字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

题解思路：

首先我们不能直接将字符串转化为int型或者BigInterger类型然后取做乘法，这样子是会超出int类型最大值的，而题目要求我们不能使用大数类型，所以我们很正常的联想到小学时学习的乘法步骤，一步一步的乘，这样可以把大数分解成零碎的小的乘法。
现在的问题就是，我们相乘后的得数如何处理，怎么处理进位的问题，以及如何将小数相乘后的结果正确的拼接起来。
一开始我想的是，每个部分拆分成小数后，乘以10或100或1000等等然后和其余部分相加，但是意识到这不是同样可能造成int类型的溢出吗，那怎么办呢。其他人的想法给了我思路，我们可以把得到的每一位的结果存放在数组中，数组大小为m+n（m，n分别为乘数的长度）；最后将数组中的数以字符串的形式拼接起来。现在的问题是，怎样将小数相乘的结果填入数组中正确的位置呢。
我们利用双指针，用i遍历第一个乘数，j遍历第二个乘数，很巧妙的我们发现，指针i和j指向位置的两个数相乘后，结果一定填入数组中第i+j和第i+j+1这两个位置。
代码中比较难理解的是为什么 res[i+j]+=sum/10; 这一位没有进位的处理，是因为即便其中的数字大于10，也会在下次循环中被重置正常，只有第一位不会，而第一位里面的数是可以大于10的，因为我们是直接拼接这些数字。

代码:

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0")||num2.equals("0")){
            return "0";
        }
        int len1=num1.length();
        int len2=num2.length();
        int[] res=new int[len1+len2];
        for(int j=len2-1;j>=0;j--){
            for(int i=len1-1;i>=0;i--){
                int num=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
                //很巧妙的发现，这两个数相乘后填入的数组的位置一定在[i+j]与[i+j+1]
                //取值相加，得到res中的值
                int sum=num+res[i+j+1];
                res[i+j+1]=sum%10;
                //这里res[i+j]中的数据是会超过10的，但是没关系，后面的循环会更新，只有当                  //其为res[0]其数据才不会被更新，但也没关系，不影响，它的值本来也可以大于10
                res[i+j]+=sum/10;
            }
        }
        //拼接
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<res.length;i++){
            //res中的第一个数可能是空的为0
            if(i==0&&res[i]==0){
                continue;
            }
            sb.append(res[i]);
        }
        return sb.toString();
    }
}