0%

leetcode每日一题-字符串相乘

Posted on In ,

字符串相乘

image1

方法一：加法

如果 $\textit{num}_1$ 和 $\textit{num}_2$之一是 0，则直接将 0 作为结果返回即可。

如果 $\textit{num}_1$ 和 $\textit{num}_2$都不是 0，则可以通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。这道题中，被乘数是 $\textit{num}_1$ ，乘数是 $\textit{num}_2$ 。需要注意的是，$\textit{num}_2$ 除了最低位以外，其余的每一位的运算结果都需要补 0。

1
class Solution {
2
    public String multiply(String num1, String num2) {
3
        if(num1.equals("0") || num2.equals("0")){
4
            return "0";
5
        }
6
        int m = num1.length(), n = num2.length();
7
        String ans = "0";
8
        for(int i=n-1; i>=0; i--){
9
            StringBuilder cur = new StringBuilder();
10
            for(int j=n-1; j>i; j--){
11
                cur.append(0);
12
            }
13
            int y = num2.charAt(i) - '0';
14
            int add = 0;
15
            for(int j=m-1; j>=0; j--){
16
                int x = num1.charAt(j) - '0';
17
                int res = x * y + add;
18
                add = res / 10;
19
                cur.append(res % 10);
20
            }
21
            if(add != 0){
22
                cur.append(add % 10);
23
            }
24
            ans = addString(ans, cur.reverse().toString());
25
        }
26
        return ans;
27
    }
28
29
    public String addString(String num1, String num2){
30
        StringBuilder sb = new StringBuilder();
31
        int m=num1.length()-1, n=num2.length()-1;
32
        int add = 0;
33
        while(m>=0 || n>=0 || add!=0){
34
            int x = m>=0 ? num1.charAt(m)-'0' : 0;
35
            int y = n>=0 ? num2.charAt(n)-'0' : 0;
36
            sb.append((x+y+add)%10);
37
            add = (x+y+add) / 10;
38
            m--;
39
            n--;
40
        }
41
        return sb.reverse().toString();
42
    }
43
}

复杂度分析：

  • 时间复杂度：$O(mn+n^2)$，乘法需要$O(mn)$的时间，字符串相加需要$O(n^2)$的时间。
  • 空间复杂度：$O(m+n)$

方法二：做乘法

方法一的时间主要浪费在字符串相加上面，为此我们可以建一个数组存储整数相乘的结果，最后再一起进位。令 $m$ 和 $n$ 分别表示 $\textit{num}_1$ 和 $\textit{num}_2$的长度，并且它们均不为 0，则 $\textit{num}_1$和 $\textit{num}_2$的乘积的长度为 $m+n-1$ 或 $m+n$。

由于 $\textit{num}_1$num 和 $\textit{num}_2$的乘积的最大长度为 $m+n$，因此创建长度为 $m+n$ 的数组 $\textit{ansArr}$ 用于存储乘积。对于任意 $0 \le i < m$ 和 $0 \le j < n$，$\textit{num}_1[i] \times \textit{num}_2[j]$的结果位于 $\textit{ansArr}[i+j+1]$，如果 $\textit{ansArr}[i+j+1] \ge 10$，则将进位部分加到 $\textit{ansArr}[i+j]$。

最后，将数组 $\textit{ansArr}$ 转成字符串，如果最高位是 0 则舍弃最高位。

1
class Solution {
2
    public String multiply(String num1, String num2) {
3
        if(num1.equals("0") || num2.equals("0")){
4
            return "0";
5
        }
6
        int m = num1.length(), n = num2.length();
7
        int[] arr = new int[m+n];
8
        for(int i=m-1; i>=0; i--){
9
            int x = num1.charAt(i) - '0';
10
            for(int j=n-1; j>=0; j--){
11
                int y = num2.charAt(j) - '0';
12
                arr[i+j+1] += x * y;
13
            }
14
        }
15
        for(int i=m+n-1; i>0; i--){
16
            arr[i-1] += arr[i] / 10;
17
            arr[i] %= 10;
18
        }
19
        int index = arr[0]==0 ? 1:0;
20
        StringBuilder sb = new StringBuilder();
21
        for(int i=index; i<m+n; i++){
22
            sb.append(arr[i]);
23
        }
24
        return sb.toString();
25
    }
26
}

复杂度分析：

  • 时间复杂度：$O(mn)$。
  • 空间复杂度：$O(m+n)$。