LeetCode 43. Multiply Strings [Medium] [C++] 解題筆記

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

EX:

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

        Output: "56088"

想法:

    這題就用一般乘法的方式解就可以了，注意進位問題。

完整程式碼:

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