Question:

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

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

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

Thinking:

  • Method:
class Solution {
    public String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int[] result = new int[len1 + len2];
        for(int i = len1 - 1; i >= 0; i--){
            for(int j = len2 - 1; j >= 0; j--){
                int temp = (num1.charAt(i) - 48) * (num2.charAt(j) - 48);
                temp += result[i + j + 1];
                result[i + j + 1] = temp % 10;
                result[i + j] += temp /10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < result.length; i++){
            if(sb.length() == 0 && result[i] == 0)
                continue;
            sb.append(result[i]);
        }
        if(sb.length() == 0)  sb.append(0);
        return sb.toString();
    }
}

二刷

  1. 确定两个数字相乘可能出现字符的最大长度。
  2. 通过两层遍历，计算出每一个位置的值（注意加上进位），并将进位放置在高位。
  3. 如果stringbuilder的长度为0，返回0。
class Solution {
    public String multiply(String num1, String num2) {
        int len1 = num1.length(), len2 = num2.length();
        int[] result = new int[len1 + len2];
        int temp = 0;
        for(int i = len1 - 1; i >= 0; i--){
            for(int j = len2 - 1; j >= 0; j--){
                temp = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + result[i + j + 1];
                result[i + j] += temp / 10;
                result[i + j + 1] = temp % 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < len1 + len2; i++){
            if(result[i] == 0 && sb.toString().length() == 0)
                continue;
            sb.append(result[i]);
        }
        if(sb.toString().length() == 0) return "0";
        return sb.toString();
    }
}