runtime 4 ms, beats 92.49% of cpp submissions
O(mn) solution with explanation

tags: string, simulation

Multiply Strings

📖 description

給定兩個由數字組成的字串，回傳他們相乘後的結果。

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

🧠 solution

使用字串模擬乘法，要注意處理修改的位數以及處理進位。

⏳ time complexity

處理兩個字串的每個位數相乘的結果，時間複雜度 O(mn) ( m 為 num1 的長度, n 為 num2 的長度)
處理字串反轉，時間複雜度為 O(2m+2n)
總時間複雜度 O(mn)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1=="0" || num2=="0"){     // 邊緣測資
            return "0";
        }
        int n = num1.size() + num2.size();
        string ans(n,'0');
        reverse(num1.begin(),num1.end());   // 反轉字串讓相乘從最低位開始
        reverse(num2.begin(),num2.end());
        int carry = 0;
        int now = 0;
        for(int i=0;i<num1.size();i++){
            for(int j=0;j<num2.size();j++){
                now = ((num1[i]-'0')*(num2[j]-'0'));    // 兩字串數值相乘
                now += (ans[i+j]-'0');                  // 加上原本內容
                carry = now/10;
                if(now>=10){
                    now%=10;
                }
                ans[i+j]=(char)(now+'0');               // 更新數值
                ans[i+j+1]+=carry;                      // 累加進位
            }
        }
        if(carry>0){
            ans.back() = carry + '0';                   // 如果最後一位有進位
        }
        while(ans.back()=='0'){                         // 處理多餘 0 
            ans.pop_back();
        }
        reverse(ans.begin(),ans.end());                 // 反轉為正常順序
        return ans;
    }
};