43. Multiply String

1 Description #

source: https://leetcode.com/problems/multiply-strings/ Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Constraints:

1 <= num1.length, num2.length <= 200
num1 and num2 consist of digits only.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.

2 Solution #

A not good solution

#include <cmath>
#include <string>
class Solution {
public:
  string multiply(string num1, string num2) {
    if (num1 == "0" || num2 == "0") {
      return "0";
    }
    int size1 = num1.size();
    int size2 = num2.size();
    auto p_str1 = num1.c_str();
    auto p_str2 = num2.c_str();
    std::string final_result;
    for (int j = size2 - 1; j >= 0; j--) {
      std::string result;
      for (int i = size1 - 1; i >= 0; i--) {
	int multiply_result = (p_str1[i] - '0') * (p_str2[j] - '0');
	result = add(result, std::to_string(multiply_result) +
		     std::string(size1 - 1 - i, '0'));
      }
      final_result =
	add(final_result, result + std::string(size2 - 1 - j, '0'));
    }
    return final_result;
  }

  std::string add(const std::string &num1, const std::string &num2) {
    auto p1 = num1.c_str();
    auto p2 = num2.c_str();
    int size1 = num1.size();
    int size2 = num2.size();
    int i = 0, j = 0, k = 0;
    std::string result = (size1 > size2 ? num1 : num2);
    auto p_res = result.c_str();
    int carry = 0;
    for (k = result.size() - 1, i = size1 - 1, j = size2 - 1; i >= 0 && j >= 0;
	 i--, j--, k--) {
      int add_result = (p1[i] - '0') + (p2[j] - '0') + carry;
      if (add_result % 10 == add_result) {
	result[k] = '0' + add_result;
	carry = 0;
      } else {
	result[k] = '0' + add_result % 10;
	carry = 1;
      }
    }

    if (i > 0) {
      for (i; i >= 0; i--, k--) {
	int add_result = carry + (p1[i] - '0');
	if (add_result % 10 == add_result) {
	  result[k] = '0' + add_result;
	  carry = 0;
	} else {
	  result[k] = '0' + add_result % 10;
	  carry = 1;
	}
      }
    } else if (j > 0) {
      for (j; j >= 0; j--, k--) {
	int add_result = carry + (p2[j] - '0');
	if (add_result % 10 == add_result) {
	  result[k] = '0' + add_result;
	  carry = 0;
	} else {
	  result[k] = '0' + add_result % 10;
	  carry = 1;
	}
      }
    } else {
      if (carry != 0) {
	if (k < 0) {
	  return '1' + result;
	} else {
	  // k should be zero
	  int add_result = 1 + (result[k] - '0');
	  if (add_result % 10 == add_result) {
	    result[k] = '0' + add_result;
	    return result;
	  } else {
	    result[k] = '0' + add_result % 10;
	    return '1' + result;
	  }
	}
      }
    }

    if (carry != 0) {
      if (k < 0) {
	result = '1' + result;
      } else {
	// k should be zero
	int add_result = 1 + (result[k] - '0');
	if (add_result % 10 == add_result) {
	  result[k] = '0' + add_result;
	} else {
	  result[k] = '0' + add_result % 10;
	  result = '1' + result;
	}
      }
    }
    return result;
  }
};