Multiply Strings

Q:
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.

A:  就是用两个数组来存储（倒序存储），并相乘

Mistakes:
1:   连乘的时候，  应该是从最低位开始。 也就是说，array1  和array 2的最后一位。(length -1 ) 开始
2： 结果的末位，总是一个0，  很奇怪！！！----------原因就是长度分别为 n1  和 n2    ---> 乘积的长度为 n1+ n2的。   那么， 如果我们都是从最后一个index 算起， 那么会导致，A[n1-1]   *A[ n2-1] 这无法表达结果的index，  （按理说，应该 i+ j -1）
--------------------解决方法：   把数字从低到高排列，然后相乘完毕，再反过来即可。

public class Solution {

    public String multiply(String num1, String num2) {
        // use two arrays to store the numbers, and multiply them
        // assume none of the input is null
        int n1 = num1.length();
        int n2 = num2.length();
        // ue two array to store them
        int[] int1 = new int[n1];
        int[] int2 = new int[n2];
        int[] result = new int[n1 + n2];

        for (int i = n1 - 1; i >= 0; i--)
            int1[i] = num1.charAt(i) - '0';

        for (int i = n2 - 1; i >= 0; i--)
            int2[i] = num2.charAt(i)- '0';

        for (int i = n2 - 1; i >= 0; i--) { // for each digits of int2,
            int[] tmp = new int[n1 + n2];
            int digit2 = int2[i];
            int carry = 0;
            for (int j = n1 - 1; j >= 0; j--) {
                int digit1 = int1[j];
                tmp[i + j + 1] = (digit1 * digit2 + carry)%10;
                carry = (digit1 * digit2 + carry) /10;
            }
            if (carry > 0) {
                tmp[i ] = carry;
            }
            addSum(result, tmp);
        }
        // change sum array to String
        // find first that is not zero
        int index = 0;
        while (index< result.length && result[index] == 0)
            index++;
        if (index  == result.length) // if result is 0
            return "0";
        else {//
            StringBuffer buf = new StringBuffer("");
            for (int i = index; i < result.length; i++)
                buf.append(result[i]);
            return buf.toString();
        }

    }

    private void addSum(int[] A, int B[]) {
        // size of A and B are the same
        int n = A.length;
        int carry = 0;
        for (int i = n - 1; i >= 0; i--) {
            int sum = A[i] + B[i] + carry;
            carry = sum / 10;
            A[i] = sum % 10;
        }
    }

}

------Mistakes:
1:   when testing whether result is 0, , in the while loop, we forget to  check whether the index is still in bound

------------------------------- 3rd-----------------------------

思路同上， 但没有先把  string 转换成 int array

public class Solution {
    public String multiply(String num1, String num2) {
        if(num1.length() ==0 || num2.length() ==0)
            return "";
        int n1 = num1.length(), n2 = num2.length();
        int[] C  = new int[n1+n2];
        for(int i =n1-1;i >=0;i--){
            int a = num1.charAt(i)-'0';
            int carry = 0;
            int j =n2-1;
            for( ;j>=0;j--){
                int b = num2.charAt(j)-'0';
                int sum = (a*b+carry+C[i+j+1])%10;
                carry = (a*b+carry+C[i+j+1])/10;
                C[i+j+1]  = sum;
            }
            while(carry !=0){
                int sum = ( C[i+j+1]+carry) %10;
                carry = ( C[i+j+1]+carry) / 10;
                C[i+j+1] = sum;
            }
        }
        // make C to string
        int index = 0;
        while (index< C.length && C[index] == 0)
            index++;
        if (index  == C.length) // if C is 0
            return "0";
            
        StringBuffer buf = new StringBuffer();
        for(int i =index;i<C.length;i++)
            buf.append(""+C[i]);
        return buf.toString().trim();
    }
}