字符串的乘积 Multiply Strings

问题：

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

解决：

①  与两个String相加类似。以289*785为例：先将它们反转

我们可以发现：

第k个位置的乘积multi = num1[i] * num2[j]+carry（其中i+j=k，0<k<m+n,0<i<m,0<j<n）。

第k个位置的值=multi%10

carry= multi/10

假设第一个数长度是m，第二个数长度是n，我们知道结果长度为m+n或者m+n-1（没有进位的情况）。

通过两个for循环，不断刷新最终的num数组，全部结束后最后得到了值。

最后将进位可能为0的第一个数组忽略，剩下的转换为字符串返回。

class Solution { //29ms
    public String multiply(String num1, String num2) {
        if(num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0)
            return "";
        if(num1.charAt(0) == '0') return "0";
        if(num2.charAt(0) == '0') return "0";
        int len1 = num1.length();
        int len2 = num2.length();
        //分别对两个开始字符串进行转置，便于后面的下标遍历 ，因为两数相乘是由个位开始的。 
        num1=new StringBuilder(num1).reverse().toString();  
        num2=new StringBuilder(num2).reverse().toString(); 
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        //从低位开始计算，最后乘积的位数为m+n-1,如果进位则是m+n  
        for (int k = 0;k < len1 + len2 -1;k ++) {
            int multi = carry;
            for (int i = 0;i <= k ;i ++ ) {//查找所有满足i+j=k的数以得到它们的乘积
                if(i < len1 && (k - i) < len2){//k-i即为j
                    multi += (num1.charAt(i) - '0') * (num2.charAt(k - i) - '0');
                }
            }
            sb.append(multi % 10);
            carry = multi / 10;
        }
        if(carry != 0) sb.append(carry);
        return sb.reverse().toString();
    }
}

② 在discuss中看到的，先将字符串转换为字符数组 ,使用一个新的数组保存每个位置乘积的和，倒序相乘。

class Solution { //22ms
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || num2.equals("0")) return "0";
        char[] num1Char = num1.toCharArray();
        int m = num1Char.length;
        char[] num2Char = num2.toCharArray();
        int n = num2Char.length;
        int[] res = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                res[i + j + 1] += (num1Char[i] - '0') * (num2Char[j] - '0');       
            }    
        }
        for (int  i = res.length - 1; i >= 1; i--) {//取得每个位置的正确的值
            int tmp = res[i] / 10;
            res[i] = res[i] % 10;
            res[i - 1] += tmp;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            if (res[i] == 0 && sb.length() == 0)
                continue;    
            sb.append((char)(res[i] + '0'));
        }
        return sb.toString();
    }
}