【数据结构基础】Leetcode 43.字符串相乘

原题链接：Leetcode 43. Multiply Strings

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"
1
2

Example 2:

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

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.

---

方法一：做加法

思路：

做竖式计算，被乘数和乘数的每一位计算后，通过加法得到最终结果
注意：计算完之后除了第一位都 需要补0

C++代码：

class Solution {
public:
    // 字符串相加
    string addStrings(string &num1, string &num2) {
        int i = num1.size() - 1, j = num2.size() - 1, add = 0;
        string ans;

        while (i >= 0 || j >= 0 || add != 0) {
            // 当位数用完时 作为0参与计算
            int x = i >= 0 ? num1[i]) - '0' : 0;
            int y = j >= 0 ? num2[j] - '0' : 0;
            int result = x + y + add;

            ans.push_back(result % 10 + '0');
            add = result / 10;
            i--;
            j--;
        }

        // 要反转过来
        reverse(ans.begin(), ans.end());
        return ans;
    }

    // 字符串相乘
    string multiply(string num1, string num2) {
        // 特判
        if (num1 == "0" || num2 == "0") {
            return "0";
        }

        string ans = "0";
        int m = num1.size(), n = num2.size();
        
        // 从右往左遍历被乘数的每一位
        for (int i = n - 1; i >= 0; i--) {
            string curr;
            // 进位
            int add = 0;
            
            // 需要补0 第一个不需要补0 第二个需要补1个0...
            for (int j = n - 1; j > i; j--) {
                curr.push_back('0');
            }
            int y = num2[i] - '0';

            // 遍历乘数的每一位
            for (int j = m - 1; j >= 0; j--) {
                int x = num1[j] - '0';
                int product = x * y + add;
                curr.push_back(product % 10 + '0');
                add = product / 10;
            }

            // 算完还有有进位时
            while (add != 0) {
                curr.push_back(add % 10 + '0');
                add /= 10;
            }

            // 要反转过来
            reverse(curr.begin(), curr.end());

            // 加法
            ans = addStrings(ans, curr);
        }
        return ans;
    }
};
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

复杂度分析：

• 时间复杂度：O(mn)，乘法做了两重循环，也就是O(mn)，加法的复杂度O(max(m,n))小个量级，忽略
• 空间复杂度：O(m + n)，乘法的最大结果是m+n位，因此存储中间状态不会超过这个范围

---

方法二：做乘法