[LeetCode] 43. Multiply Strings

Posted on | In

Problem

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:

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

Example 2:

1
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.

Explanation

  1. When two numbers are multiple, the result’s length will be maximum of len(num1)+len(num2).

  2. When we multiple two numbers, we start from the lowest digit. When we multiple two lowest digits, its result will be maximum of two digits, and this result’s lowest digit’s index will be indexOf(digit1)+indexOf(digit2)+1, the highest digit’s index will be indexOf(digit1)+indexOf(digit2).

  3. For example, if two input numbers are 23 and 45. We have the following operations:

    1
    2
    3
    4
    5
    6
    7
         2 3 <- num1
     4 5 <- num2
 0 0 0 0 <- result
 0 0 1 5 <- 5*3
 0 1 1 5 <- 5*2
 0 2 3 5 <- 4*3
 1 0 3 5 <- 4*2

  4. After we get the result array, we create a string builder. Then loop through the result array, if the iterated element is 0 and string builder’s length is also 0, that means the current element is a leading zero, so we ignore it. At the end, if the string builder’s length is 0, then we return 0; else we return the string builder’s string format.

Solution

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
class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int len1 = num1.length();
        int len2 = num2.length();
        int[] res = new int[len1+len2];
        for (int i = len2-1; i >= 0; i--) {
            for (int j = len1-1; j >= 0; j--) {
                int loPos = i+j+1;
                int hiPos = i+j;
                int mul = (num2.charAt(i)-'0') * (num1.charAt(j)-'0') + res[loPos];
                res[loPos] = mul%10;
                res[hiPos] += mul/10;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (int e : res) {
            if (e==0 && sb.length() ==0) continue;
            sb.append(e);
        }
        if (sb.length() == 0) return "0";
        return sb.toString();
    }
}