43. Multiply Strings

Link

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:

1. The length of both num1 and num2 is < 110.

2. Both num1 and num2 contain only digits 0-9.

3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.

4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution

n1位數跟n2位數的乘機最多就是n1+n2位數。 999 * 999 <= 999 * 1000 <= 999000 , 3位數乘3位數最多六位數

概念是用把每個位數乘法的值先存到array[n1+n2+1]中，然後之後處理溢位問題。 其中n1是a.length(), n2是b.length()，

public String multiply(String num1, String num2) {
        int n1 = num1.length(), n2 = num2.length();
        int[] product = new int[n1+n2];
        for(int i = n1-1; i >= 0; i--){
            for(int j = n2-1; j >= 0; j--){
                
                product[i+j+1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                
            }
        }
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = n1+n2-1; i >= 0; i--){
            int sum = product[i] + carry;
            sb.append(sum%10);
            carry = sum/10;
        }
        if(carry != 0){
            sb.append(carry);
        }
        
        //特別處理是0開頭的結果。
        while(sb.length() != 0 && sb.charAt(sb.length()-1) == '0' )
        {
            sb.deleteCharAt(sb.length()-1);
        }
        
        return sb.length() == 0? "0": sb.reverse().toString();
        
    }