力扣 43 字符串相乘

题意：给定两个正的数字字符串，只用加法计算两字符串的乘积

思路：比如98，89

1. 计算数组中每两个数的乘积，并把乘积加入到对应的index
   ［0，72，145，72］
2. 处理每一个product元素，使每一位都是一个数字
   ［8，7，2，2］
3. 把每一位的数字加入的结果
   8722
4. 移除头部的0

思想：数学计算＋字符串匹配

复杂度：时间O(n²)，空间O(n)

public class Solution {
     public String multiply(String num1, String num2) {
        int n1 = num1.length(), n2 = num2.length();
        // 结果数组
        int[] products = new int[n1 + n2];
        // 计算数组中每两个数的乘积，并把乘积加入到对应的index
        for (int i = n1 - 1; i >= 0; i--) {
            for (int j = n2 - 1; j >= 0; j--) {
                int d1 = num1.charAt(i) - '0';
                int d2 = num2.charAt(j) - '0';
                products[i + j + 1] += d1 * d2;
            }
        }
        int carry = 0;
        // 处理每一个product元素，使每一位都是一个数字
        for (int i = products.length - 1; i >= 0; i--) {
            int tmp = (products[i] + carry) % 10;
            carry = (products[i] + carry) / 10;
            products[i] = tmp;
        }
        // 结果字符串
        StringBuilder sb = new StringBuilder();
        // 把每一位的数字加入的结果
        for (int num : products) sb.append(num);
        // 移除头部的0
        while (sb.length() != 0 && sb.charAt(0) == '0') sb.deleteCharAt(0);
        return sb.length() == 0 ? "0" : sb.toString();
    }
}