# 43 - Multiply Strings

解法一 - 利用各部分結果的位置來有效率儲存計算結果

我們知道長度 m 的 num1 跟長度 n 的 num2 相乘，最長就是 m+n。而且我們知道從右到左每一位乘完的結果會一直往左遞增。

如果我們把圖畫出來：

可以看到最重要的規律就是

num1[i] * num2[j] 的結果會被存在儲存結果 array 的 [i + j, i + j + 1] 。

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1 == "0" || num2 == "0") return "0";

        int m = num1.length(), n = num2.length();
        vector<int> pos(m+n, 0);

        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;
                int sum = mul + pos[p2];

                pos[p1] += sum/10;
                pos[p2] = sum%10;

                // If implement in the way below, we have to deal with carry 
                // int sum = mul;

                // pos[p1] += sum/10;
                // pos[p2] += sum%10;
            }
        }

        string res;
        for(auto &p:pos) if(!(res.empty() && p == 0)) res += to_string(p);
        return res;
    }
};