字符串相乘

QUESTION:

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

EXPLANATION:

思路的话其实就是小学时候学习的乘法思路:
1.首先将num1的每一位与num2的每一位相乘,得到temp的数组
2.将temp数组的每一个index进行相加,得到最后的result
3.别忘记去除头部的0

SOLUTION:

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.length()==0 || num2.length()==0) return num1.length()==0?num2:num1;
        int index = 0;
        String[] temp = new String[num2.length()];
        while (index<num2.length()){
            int tmpIndex = 0;
            int carry = 0;
            int a = Integer.parseInt(num2.charAt(num2.length()-1-index)+"");
            StringBuilder sb = new StringBuilder();
            while (tmpIndex<num1.length()){
                String b="";
                if(tmpIndex<num1.length()) b+= num1.charAt(num1.length()-1-tmpIndex);
                int bi = 1;
                if(!b.isEmpty()) bi = Integer.parseInt(b);
                int result = a * bi + carry;
                carry = result / 10;
                sb.insert(0,result % 10);
                tmpIndex++;
            }
            if(carry!=0)sb.insert(0,carry);
            for(int i = index;i>0;i--) sb.append(0);
            temp[index] = sb.toString();
            index++;
        }
        StringBuilder result = new StringBuilder();
        index = 0;
        int carry = 0;
        while (index < temp[temp.length-1].length()){
            int tmp = 0;
            for(int i = 0;i<temp.length;i++){
                if(temp[i].length()-1-index <0) continue;
                tmp += Integer.parseInt(temp[i].charAt(temp[i].length()-1-index)+"");
            }
            tmp+=carry;
            result.insert(0,tmp % 10);
            carry = tmp / 10;
            index++;
        }
        if(carry!=0) result.insert(0,carry);
        index = 0;
        while (result.charAt(index)=='0' && index < result.length()-1) index++;
        return result.substring(index,result.length());
    }
}