Leetcode-43. 字符串相乘

43. 字符串相乘
给定两个以字符串形式表示的非负整数 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）或直接将输入转换为整数来处理。

解题思路：我们需要利用程序模拟竖式相乘的过程
我们可以用一个数组来表示：res
**
**最后我们只需要确认乘积在结果数组中的下标和i和j的关系即可
不难得出：num1【i】和num2【j】的乘积在res中的下标为i+j和i+j+1.其中（i+j+1为低位）
那么res最多有m+n位。我们求结果时需要先排除前边的0.

class Solution {
    public String multiply(String num1, String num2) {
        int m=num1.length();
        int n=num2.length();
        int[] res=new int[m+n];
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                int mul=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
                int p1=i+j+1;
                int p2=i+j;
                //累加结果到res数组：其中p1为低位下标，p2为高位
                int sum=res[p1]+mul;
                res[p1]=sum%10;
                res[p2]+=sum/10;
            }
        }
        //去除结果数组前侧的0
        int i=0;
        while(i<res.length && res[i]==0){
            i++;
        }
        //求得结果
        String str="";
        for(;i<res.length;i++){
            str+=res[i];
        }
        //如果字符串为空，应该返回0
        return str.length()==0?"0":str;
    }
}