问题描述

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.

思路分析

我的思路是完全模拟手算乘法，每次用乘数的一位乘以被乘数，与结果相加。这样做可以AC但是很慢（66 ms，只能beats 7.19%）。
参考了ChiangKaiShrek的解法 ，按位累加即可，不用每次都创建新的string来进行累加。

AC代码

class Solution {
public:
    string multiply(string num1, string num2) {
        int len1 = num1.size();
        int len2 = num2.size();
        string rst(len1+len2, '0');
        for (int i = len1-1; i >= 0; --i){
            int carry = 0;
            for (int j = len2-1; j >= 0; --j){
                int tmp = (rst[i+j+1] - '0') + (num1[i]-'0') * (num2[j]-'0') + carry;
                rst[i+j+1] = char(tmp % 10 + '0');
                carry = tmp / 10;
            }
            rst[i] += carry;
        }
        int i;
        for(i = 0; i < len1+len2; ++i)
            if (rst[i] != '0')
                break;
        if (i == len1+len2)
            return "0";
        return rst.substr(i);
        }
};

Runtime: 6 ms, which beats 78.05% of cpp submissions.

得到”按位累加”的启发后改进了自己的思路，也取的了不错的效果。

string multiply(string num1, string num2) {
    if (num1 == "0" || num2 == "0")
        return "0";
    int len1 = num1.size();
    int len2 = num2.size();
    string rst_s(len1+len2, '0');
    vector<int> rst(len1+len2);

    for (int i = len1 - 1; i >= 0; i--){
        for (int j = len2 - 1; j >= 0; j--) {
            rst[i+j+1] += (num1[i] - '0') * (num2[j] - '0');
        }
    }
    int carry = 0;
    int i = len1+len2-1;
    while (i >= 0){
        rst_s[i] = char(((carry + rst[i]) % 10) + '0');
        carry = (carry + rst[i]) / 10;
        --i;
    }
    i = 0;
    while (i < len1+len2 && rst_s[i] == '0')
        ++i;

    return rst_s.substr(i);
}

同样Runtime: 6 ms, which beats 78.05% of cpp submissions.