LeetCode43 字符串相乘

题意

实现高精度乘法

解法

num1的第i位(高位从0开始)和num2的第j位相乘的结果在乘积中的位置是[i+j, i+j+1]
例: 123 * 45, 123的第1位 2 和45的第0位 4 乘积 08 存放在结果的第[1, 2]位中

代码

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1.size() < num2.size()) {
            swap(num1, num2);
        }
        int n = num1.size(), m = num2.size();
        if (n == 0 || m == 0) return "";
        vector<int> ans(n + m);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                int temp = (num1[i] - '0') * (num2[j] - '0');
                temp += ans[i + j + 1];
                ans[i + j] += temp / 10;
                ans[i + j + 1] = temp % 10;
            }
        }
        int idx = 0;
        while(idx < ans.size() - 1 && ans[idx] == 0) {
            idx++;
        }
        string ret = "";
        for ( ; idx < ans.size(); idx++) {
            ret += to_string(ans[idx]);
        }
        return ret;
    }
};