【暴力】字符串相乘

## 题目

43. 字符串相乘

---

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

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1：

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

示例 2：

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

提示：

• 1 <= num1.length, num2.length <= 200
• num1 和 num2 只能由数字组成。
• num1 和 num2 都不包含任何前导零，除了数字0本身。

解题

方法一：模拟 竖式相乘

思路

从后向前遍历两个字符串，模拟竖式相乘，把每一位乘起来转为字符串构造器并向后补对应位数的零，然后加和进最终结果（注意要使用字符串加和，否则字符串的位数可能会过大，字符串相加见415. 字符串相加）。

代码

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        char[] num1Arr = num1.toCharArray(), num2Arr = num2.toCharArray();
        int len1 = num1Arr.length, len2 = num2Arr.length;
        String ans = "0";
        for (int i = 0; i < len1; i++) {
            int curr = num1Arr[len1 - 1 - i] - '0';
            for (int j = 0; j < len2; j++) {
                StringBuilder product = new StringBuilder(String
                    .valueOf(curr * (num2Arr[len2 - 1 - j] - '0')));
                for (int k = 0; k < i + j; k++) {
                    product.append("0");
                }
                ans = addStrings(ans, product.toString());
            }
        }
        return ans;
    }

    public String addStrings(String num1, String num2) {
        int idx1 = num1.length(), idx2 = num2.length();
        StringBuilder ans = new StringBuilder();
        int carry = 0;
        while(--idx1 >= 0 | --idx2 >= 0 || carry != 0) {
            int digit1 = idx1 >= 0 ? num1.charAt(idx1) - '0' : 0;
            int digit2 = idx2 >= 0 ? num2.charAt(idx2) - '0' : 0;
            int currDigit = carry + digit1 + digit2;
            carry = currDigit / 10;
            ans.append(currDigit % 10);
        }
        return ans.reverse().toString();
    }
}