[LeetCode] 43. Multiply Strings

[frdmu]

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.

 

解法：
代码如下：

class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.size();
        int n = num2.size();
        vector<int> vec(m+n);
        string res;
 
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                int mul = (num1[i] - '0') * (num2[j] - '0');
                int p1 = i + j, p2 = i + j + 1, sum = mul + vec[p2];
                vec[p2] = sum % 10; 
                vec[p1] += sum / 10;
            }
        }
       
        for (int v: vec) {
            if (!res.empty() || v != 0) res.push_back(v+'0');
        }
        
        return res.empty()? "0" : res;
    }
};

Refer：
43. Multiply Strings