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.

Solution:

num1[i] * num2[j] will be placed at position [i+j] and [i+j+1]

1. create new array with length num1_length + num2_length
2. do multiply, sum the multiplication result with value at position [i+j+1] first, then use the sum to calculate the digit and carry to be placed at [i+j+1] and [i+j]
3. skip all leading zeros, convert the rest to string

public class Solution {
    public String multiply(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        if(num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0){
            return sb.toString();
        }

        int len1 = num1.length();
        int len2 = num2.length();
        int[] res = new int[len1+len2];
        for(int i = len1 - 1; i >= 0; i--){
            for(int j = len2 -1; j >= 0; j--){
                int multiply = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int sum = multiply + res[i+j+1];
                int digit = sum % 10;
                int carry = sum / 10;

                res[i+j] += carry;
                res[i+j+1] = digit;
            }
        }

        for(int e : res){
            if(!(e == 0 && sb.length() == 0)){
                sb.append(e);
            }
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

4.References:
https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation