字符串相乘

43. 字符串相乘

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

示例 1:

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

示例 2:

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

说明：

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

我们可以模拟竖式计算来得到最后的结果。

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")){
            return "0";
        }
        
        //使用 num1 的每一位乘 num2
        int len1 = num1.length(), len2 = num2.length();
        String ans = "0";
        //从 num1 的最后一位开始
        for(int i = len1 - 1; i >= 0; i--){
            StringBuffer sb = new StringBuffer();
            int carry = 0;
            //添加尾部的 0 
            for(int j = len1 - 1; j > i; j--){
                sb.append(0);
            }
            //计算乘积
            int x = num1.charAt(i) - '0';
            for(int j = len2 - 1; j >= 0; j--){
                int y = num2.charAt(j) - '0';
                int num = x * y + carry;
                sb.append(num % 10);
                carry = num / 10;
            }
			//如果最后有进位，就将结果加入
            if(carry != 0){
                sb.append(carry % 10);
            }
            //结果相加
            ans = addStrings(ans, sb.reverse().toString());
        }
        return ans;
    }
	//字符串相加
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1;
        int carry = 0;
        StringBuffer sb = new StringBuffer();
        while(i >= 0 || j >= 0 || carry == 1){
            int x = i >= 0 ? num1.charAt(i--) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j--) - '0' : 0;
            int num = x + y + carry;
            carry = num / 10;
            sb.append(num % 10);
        }
        return sb.reverse().toString();
    }
}

时间复杂度O(mn)，空间复杂度O(m + n)。

我们可以优化竖式计算，num1 位数为 m，num2 位数为 n，num1 * num2 的最大总位数为 m * n。num1[i] * num2[j] 的结果为 tmp（可能为一位或者两位数），第一位位于 res[i + j]，第二位位于 res[i + j + 1]。

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")){
            return "0";
        }
        int[] res = new int[num1.length() + num2.length()];
        for(int i = num1.length() - 1; i >= 0; i--){
            int x = num1.charAt(i) - '0';
            
            for(int j = num2.length() - 1; j >= 0; j--){
                int y = num2.charAt(j) - '0';
                int num = x * y + res[i + j + 1];
                res[i + j + 1] = num % 10;
                res[i + j] += num / 10;
            }
        }

        StringBuffer ans = new StringBuffer();
        for(int i = 0; i < res.length; i++){
            if(i == 0 && res[i] == 0) continue;//第一位如果为 0，去掉第一位的 0
            ans.append(res[i]);
        }
        return ans.toString();
    }

}

时间复杂度O(mn)，空间复杂度O(m + n)。