43. Multiply Strings

Leetcode Math String

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

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

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

Note:

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

分析

两个数相乘，以我们小学时学的方法：

1. 将第二个数字的每个数与第一个数相乘
2. 将第一步的结果相加

例如296*31。

仿照这个步骤，构造两个循环。内循环计算步骤1，外循环计算步骤2。add()是将两个数相加的方法。

public String multiply(String num1, String num2) {
    StringBuilder s = new StringBuilder("0");
    char[] n1 = num1.toCharArray(), n2 = num2.toCharArray();
    int carry = 0, l1 = num1.length(), l2 = num2.length();
    int i = 0;
    while (i < l1) {
        int j = 0;
        StringBuilder t = new StringBuilder();
        while (j < l2 || carry != 0) {
            int num = 0;
            if (j < l2) num += (n1[l1 - i - 1] - '0') * (n2[l2 - j - 1] - '0');
            num += carry;
            carry = num / 10;
            num = num % 10;
            t.append(num);
            j++;
        }
        t.reverse();
        for (int k = 0; k < i; k++)
            t.append("0");
        s = add(s, t);
        i++; 
    }
    if (s.charAt(0) == '0') return "0";
    return s.toString();

}

private StringBuilder add(StringBuilder num1, StringBuilder num2) {
    StringBuilder s = new StringBuilder();
    int carry = 0, l1 = num1.length(), l2 = num2.length();
    int i = 0;
    while (i < l1 || i < l2 || carry != 0) {
        int num = 0;
        if (i < l1) num += num1.charAt(l1 - i - 1) - '0';
        if (i < l2) num += num2.charAt(l2 - i - 1) - '0';
        num += carry;
        if (num > 9) {
            num -= 10; carry = 1;
        } else carry = 0;

        s.append(num);
        i++;
    }
    return s.reverse();
}

这种方法虽然比较直接，但是运算速度慢，主要原因是

• 每个中间结果都用字符串保存，空间复杂度增加
• 字符串反复遍历，时间复杂度增加

有一种非常简单、优雅的方法，它利用了两个数相乘以后(步骤1)在结果中的相对位置，而且是一个数和一个数相乘，简化了复杂的内循环。

根据上图可以看到： num1[i] * num2[j] 的结果会在 [i + j, i + j + 1] 的位置上。

public String multiply(String num1, String num2) {
    int l1 = num1.length(), l2 = num2.length();
    int[] pos = new int[l1 + l2];
    for(int i = l1 - 1; i >= 0; i--) {
        for(int j = l2 - 1; j >= 0; j--) {
            int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); 
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + pos[p2];

            pos[p1] += sum / 10;
            pos[p2] = (sum) % 10;
        }
    }  

    StringBuilder s = new StringBuilder();
    for(int p : pos) 
        // special occasion: like "0000"
        if(!(s.length() == 0 && p == 0)) s.append(p);
    return s.length() == 0 ? "0": s.toString();
}