Description

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution

找规律

这道题目也蛮有意思的。仔细想来，乘法是怎么做的呢？

其实对两个数做乘法，实际上就是将两个数的位置两两组合做乘法，然后求和。对于num1的i位，和num2的j位，由于是两个一位数相乘，所以乘积一定在两位数之内，所摆放到的位置就是i + j和i + j + 1这两个位置上。

要注意对于carry的处理。p1和p2都可能会有carry哦。

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        int[] pos = new int[m + n];
        
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                int p1 = i + j;
                int p2 = i + j + 1;
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + pos[p2];
                pos[p1] += mul / 10;
                pos[p2] = mul % 10;
            }
        }
        
        StringBuilder res = new StringBuilder();
        for (int p : pos) {
            if (res.length() == 0 && p == 0) {
                continue;
            }
            res.append(p);
        }
        return res.length() == 0 ? "0" : res.toString();
    }
}