Leetcode P0043"Multiply Strings" 题解

博文中会简要介绍Leetcode P0043题目分析及解题思路。

“Multiply Strings”是一道考验基本功的题目，需要注意细节，也需要有耐心。

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.

具体的解法可以参照下面的代码中的注释。需要注意的是，两个数相乘，得到的最终结果的位数不会超过两个数的位数之和再加上1。

以下是Java的题解代码实现。

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.length() == 0 || num2.length() == 0)
            return "";
        
        char[] chars1 = num1.toCharArray(), chars2 = num2.toCharArray();
        int len1 = chars1.length, len2 = chars2.length;
        if (chars1[0] == '0' || chars2[0] == '0') 
            return "0";
        
        char[] product = new char[len1+len2+1];
        for (int idx=0; idx<product.length; ++idx) 
            product[idx] = '0';
        
        for (int i1=len1-1; i1>=0; --i1) {
            // tail表示当前正在计算的最终结果product的位置
            int increment = 0, j2 = len2-1, d1 = chars1[i1]-'0', tail = product.length-(len1-i1);
            while (j2 >= 0 || increment > 0) {
                int d2 = (j2 >= 0)? chars2[j2]-'0': 0;
                
                // 当前结果数字等于d1*d2加上进位加上原结果对应位置上的数字
                int r = d1*d2+increment+(product[tail]-'0');
                increment = r/10;
                r = r%10;
                
                product[tail] = (char) (r+'0');
                --tail;
                --j2;
            }
            
        }
        
        int start = 0;
        while (product[start] == '0')
            ++start;
        
        String ret = String.valueOf(product).substring(start);
        return ret;
    }
}

聖地亞歌

Leetcode P0043"Multiply Strings" 题解

Search

Table of Contents