Leetcode43. 字符串相乘

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

1
2
输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

1
2
输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

  1. num1 和 num2 的长度小于110。
  2. num1 和 num2 只包含数字 0-9。
  3. num1 和 num2 均不以零开头，除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

解题思路

方法一 列竖式计算法

算法详述

这道题最常见的解法就是模拟列竖式计算的方法进行计算两个字符串的值。

如上图所示，当nums1和nums2均不为0的时候，将nums1和nums2分别视为被乘数和乘数，从右往左遍历乘数，将乘数的每一位与被乘数相乘得到相应的结果，然后将每次得到的结果累加得到最终的答案。

如果nums1和nums2至少有一个为0，那么直接返回0即可。

示例代码

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
string addString(string& nums1, string& nums2){
    int i = nums1.size() - 1;
    int j = nums2.size() - 1;
    int add = 0;
    string ans;

    while(i >= 0 || j >= 0 || add != 0){
        int x = i >= 0 ? nums1[i] - '0' : 0;
        int y = j >= 0 ? nums2[j] - '0' : 0;
        int res = x + y + add;

        ans.push_back(res % 10 + '0');
        add = res / 10;

        i--;
        j--;
    }

    reverse(ans.begin(), ans.end());
    return ans;
}

string multiply(string& nums1, string& nums2){
    if(nums1 == "0" || nums2 == "0"){
        return "0";
    }

    string ans = "0";
    int m = nums1.size();
    int n = nums2.size();
    for(int i = n - 1; i >= 0; --i){
        string tmp;
        int add = 0;
        for(int j = n - 1; j > i; --j){
            tmp.push_back(0 + '0');
        }

        int y = nums2[i] - '0';
        for(int j = m - 1; j >= 0; --j){
            int x = nums1[j] - '0';
            int res = x * y + add;
            tmp.push_back(res % 10 + '0');
            add = res / 10;
        }
        while(add != 0 ){
            tmp.push_back(add % 10 + '0');
            add /= 10;
        }

        reverse(tmp.begin(), tmp.end()); 
        ans = addString(ans, tmp);  
    }
    return ans;
}

复杂度分析

时间复杂度为：O(mn+n2)O(mn+n^2)，其中 mm 和 nn分别是 nums1和nums2的长度

空间复杂度为：O(m+n)O(m+n)，其中 mm 和 nn分别是 nums1和nums2的长度

方法二 优化后的列竖式计算法

算法详述

一般列竖式计算的做法是从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。在相加的过程中，相加的字符串的长度分别为m,m+1,⋯ ,m+nm,m+1, \cdots,m+n,因而相加的平均字符串长度为n(2m+n)2\frac{n(2m+n)}{2}，而相加的次数一共为nn次，两者相乘后可以得到总体的时间复杂度为O(mn+n2)O(mn+n^2)，太过耗时。而且观察得知，主要在于相加的过程耗时。所以我们可以从这方面下手进行优化。

如果将被乘数和乘数的每一位分别进行相乘，并且将相乘的结果使用数组代替字符串存储结果，那么可以简化为至多两位数加法运算，减少了对字符串的操作。

令 mm 和 nn 分别表示 nums1和nums2的长度,并且它们均不为 0，则nums1和nums2的乘积的长度为$ m+n-1$ 或 m+nm+n。

上述结论的简单证明如下：

  • 如果nums1和nums2都取最小值，则nums1=10m−1,num2=10n−1,nums1×nums2=10m+n−2nums1 = 10^{m-1},num2 = 10^{n-1},nums1 \times nums2 = 10^{m+n-2}，乘积的长度为m+n−1m+n-1；
  • 如果nums1和nums2都取最大值，则nums1=10m−1,num2=10n−1,nums1×nums2=10m+n−10m−10n+1nums1 = 10^{m}-1,num2 = 10^{n}-1,nums1 \times nums2 = 10^{m+n}-10^{m}-10^{n}+1，乘积显然小于10m+n10^{m+n}且大于10m+n−110^{m+n-1}，所以乘积的长度为m+nm+n；

由于nums1和nums2的乘积的长度最多为m+nm+n，因此可以创建长度为m+nm+n的数组ans存储乘积。对于任意的0≤i≤m0 \leq i \leq m和0≤j≤n0 \leq j \leq n，nums1[i]×nums2[j]nums1[i] \times nums2[j]的结果存储在ans[i+j+1]ans[i+j+1]，如果ans[i+j+1]≥10ans[i+j+1] \geq 10，则将进位的部分加到ans[i+j]ans[i+j]。

过程可以参见下图：

最后还需要将ans数组转化为字符串，如果最高位为0的话还需要舍弃最高位。

实例代码

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
string multiply(string& nums1, string& nums2){
    if(nums1 == "0" || nums2 == "0"){
        return "0";
    }

    vector<int> ans(nums1.size() + nums2.size(), 0);
    for(int i = nums1.size() - 1; i >= 0; --i){
        int x = nums1[i] - '0';
        for(int j = nums2.size() - 1; j >= 0; --j){
            int y = nums2[j] - '0';
            ans[i + j + 1] += x * y;
            if(ans[i + j + 1] > 9){
                ans[i + j] += ans[i + j + 1] / 10;
                ans[i + j + 1] %= 10;
            }
        }
    }

    string ansStr;
    int index = 0;
    if(ans[0] == 0) index++;
    while(index < ans.size()){
        ansStr += (ans[index] + '0');
        index++;
    }

    return ansStr;
}

复杂度分析

时间复杂度为：O(mn)O(mn)，其中 mm 和 nn分别是 nums1和nums2的长度

空间复杂度为：O(m+n)O(m+n)，其中 mm 和 nn分别是 nums1和nums2的长度