43. Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Converting the input string to integer is NOT allowed.

You should NOT use internal library such as BigInteger.

one solution is to use add, for each i in num1, do an addition to num2, then build the result as add two string.

second is to notice the property of multiply, which is each postions result is added up by using different postion combination in num1 and num2, which is:

  num3[i+j+1] = num1[i] * num2[j] + carry + num3[i+j+1]

why need to add it self ? cause in any [i, j ] round, num3[i+j+1] may already been calculated, such as, [i-1, j+1], in this way, there is already a value.

public class Solution {
    public String multiply(String num1, String num2) {

        int l1 = num1.length();
        int l2 = num2.length();
        int l3 = l1 + l2;
        int[] num3 = new int[l3];

        for(int i= l1-1; i>=0; i--){
            int carry = 0;
            int j =l2-1;
            for(; j>=0; j--){
                int res = carry + num3[i+j+1] +
                            (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                num3[i+j+1] = res%10;
                carry = res /10;
            }

            num3[i+j+1] = carry; // the carry need to carry to next position. since j is now -1, so nums3[i+j+1] means nums[i+j+1 - 1]. from backward it is the next position need the carry. SO ASSIGNED, NOT APPEND.
        }

        int i=0;
        for(; i< l3; i++){
            if(num3[i] != 0) break;
        }

        if(i == l3)  return "0";
        StringBuilder sb = new StringBuilder();
        while(i < l3){
            sb.append(num3[i++]);
        }

        return sb.toString();

    }
}