43. Multiply Strings

• Difficulty: Medium

• Topics: Math, String

• Similar Questions:

  • Add Two Numbers

  • Plus One

  • Add Binary

  • Add Strings

Problem:

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

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

Example 2:

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

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contain only digits 0-9.
3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solutions:

class Solution {
public:
    string multiply(string num1, string num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        if (num1 == "0" || num2 == "0") return "0"; // this check is important

        vector<int> digits (len1 + len2, 0);

        for (int i = 0; i < len1; ++i) {
            for (int j = 0; j < len2; ++j) {
                digits[i + j + 1] += (num1[i] - '0') * (num2[j] - '0'); // remeber the position of digits.
            }
        }
        string ret;
        for (int i = digits.size() - 1; i > 0; --i) {
            int digit = digits[i] % 10;
            digits[i-1] += digits[i]/10;
            ret.push_back(digit + '0');
        }

        if (digits[0] > 0)  ret.push_back(digits[0] + '0');

        reverse(ret.begin(), ret.end());
        return ret;
    }
};

Another more concise solution

It is possible to aggregate sum and carry.

From Huahua

// Author: Huahua
// Running time: 4 ms
class Solution {
public:
  string multiply(string num1, string num2) {
    const int l1 = num1.length();
    const int l2 = num2.length();
    string ans(l1 + l2, '0');
    for (int i = l1 - 1; i >= 0; --i)
      for (int j = l2 - 1; j >= 0; --j) {
        int sum = (ans[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0');        
        ans[i + j + 1] = (sum % 10) + '0';
        ans[i + j] += sum / 10; // This line is not a problem if the order is from right to left
      }

    // ans[0] is guaranteed to be less than 10 due to math property
    for (int i = 0; i < ans.length(); ++i)
      if (ans[i] != '0' || i == ans.length() - 1) return ans.substr(i);
    return "";
  }
};