IT博客汇 | 43. Multiply Strings

43. Multiply Strings

10k发表于 2023-09-05 00:00:00

Question

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

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Algorithm

This question is straightforward actually. You just need to implement how the multiplication works. The key point is to figure out how the digits mapping.

Figure out the details in the standard solution with explanation.

Code

class Solution {
    public String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int[] resArr = new int[len1 +len2];
        int carry = 0;
        for (int i = 0; i < num1.length(); i++) {
            for (int j = 0; j < num2.length(); j++) {
                int n1 = num1.charAt(len1 - 1 - i) - '0';
                int n2 = num2.charAt(len2 - 1 - j) - '0';
                int cur = (n1 * n2 + carry) % 10;
                carry = (n1 * n2 + carry) / 10;
                
                carry += (resArr[len1 + len2 - 1 - i-j] + cur) / 10;
                resArr[len1 + len2 - 1 - i-j] = (resArr[len1 + len2 - 1 - i-j] + cur) % 10;
            }
            resArr[len1 - i - 1] += carry;
            carry = 0;
        }
        
        if (carry != 0) {
            resArr[0] += carry;
        }
        
        StringBuilder sb = new StringBuilder();
        boolean flag = false;
        for (int x = 0; x < resArr.length; x++) {
            if (flag) {
                sb.append(String.valueOf(resArr[x]));
            } else {
                if (resArr[x] != 0) {
                    flag = true;
                    sb.append(String.valueOf(resArr[x]));
                }
            }
        }
        return "".equals(sb.toString()) ? "0" : sb.toString();
    }
}