43. Multiply Strings

题目链接

https://leetcode.com/problems/multiply-strings/

解题思路

两个数组倒着相乘。

代码

class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int> v(num1.length() + num2.length(), 0);
        int carry, t, k;
        for (int i = num1.length() - 1, p = 0; i >= 0; --i, p++) {
            int a = num1[i] - '0';
            if (a == 0) {
                continue;
            }
            k = p;
            carry = 0;
            for (int j = num2.length() - 1; j >= 0; --j, k++) {
                int b = num2[j] - '0';
                t = a * b + carry;
                carry = t / 10;
                t = t % 10;
                v[k] += t;
                if (v[k] >= 10) {
                    v[k] -= 10;
                    carry++;
                }
            }
            v[k] = carry;
        }
        string ans;
        t = v.size() - 1;
        while (t >= 0 && v[t] == 0) {
            t--;
        }

        for (; t >= 0; t--) {
            ans += (char)(v[t] + '0');
        }

        if (ans.length() == 0) {
            ans += '0';
        }
        return ans;
    }
};