43. Multiply Strings

发表于 | 分类于

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

解法1：

按位相乘，注意把中间结果要存储在一个res[length1 + length2]的数组里。
然后从后往前扫描，比较容易错的是对应的res的数组的位置。要特别注意一下。
C++

1

Java

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
public class Solution {
public String multiply(String num1, String num2) {
        if (num1.length() == 0 || num2.length() == 0) {
            return "";
        }
        int[] digits = new int[num1.length() + num2.length()];
        // Start from the last digit in num2, i.e. the bottom one
        for (int i = num2.length() - 1; i >= 0; i--) {
            int carry = 0;
            for (int j = num1.length() - 1; j >= 0; j--) {
                int temp = carry + (num1.charAt(j) - '0')*(num2.charAt(i) - '0') + digits[num2.length() - 1 - i + num1.length() - 1 -j];
                digits[num2.length() - 1 - i + num1.length() - 1 -j] = temp % 10;
                carry = temp / 10;
            }
            if (carry != 0) {
                digits[num1.length() + num2.length() - 1 - i] = carry;
            }
        }
        int i = 0, j = digits.length - 1;
        while (i < j) {
            int temp = digits[i];
            digits[i] = digits[j];
            digits[j] = temp;
            i++;
            j--;
        }
        StringBuilder builder = new StringBuilder();
        for (int k = 0; k < digits.length; k++) {
            if (builder.length() == 0 && digits[k] == 0) {
                continue;
            }
            builder.append(digits[k]);
        }
        if (builder.length() == 0) {
            builder.append(0);
        }
        return builder.toString();
    }
}

精简很多的code的写法：

lang: java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        int[] res = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int index1 = i + j, index2 = i + j + 1;
                int sum = mul + res[index2];
                res[index1] += sum / 10;
                res[index2] = (sum % 10);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int num : res) {
            if (!(sb.length() == 0 && num == 0)) sb.append(num);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}