题目描述

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

解法

解法1：我的解法

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        string result;
        int cnt = 0;
        for (int i = num2.size() - 1; i >= 0 ; i--) {
            string val = mul(num1, num2[i]);
            for (int i = 0; i < cnt; i++) {
                val.push_back('0');
            }
            result = add(result, val);
            cnt++;
        }
        return result;
    }

    string mul(string num, char c) {
        string result;
        int carry = 0;
        for (int i = num.size() - 1; i >= 0; i--) {
            int res = (num[i] - '0') * (c - '0') + carry;
            carry = res / 10;
            int val = res % 10;
            result.insert(0, 1, val + '0');
            //result = to_string(val) + result;
        }
        if (carry > 0) {
            result.insert(0, 1, carry + '0');
            //result = to_string(carry) + result;
        }
        return result;
    }

    string add(string num1, string num2) {
        string result;
        int index1 = num1.size() - 1;
        int index2 = num2.size() - 1;
        int carry = 0;
        while (index1 >=0 && index2 >= 0) {
            int res = (num1[index1] - '0') + (num2[index2] - '0') + carry;
            carry = res / 10;
            int val = res % 10;
            //result = to_string(val) + result;
            result.insert(0, 1, val + '0');
            index1--;
            index2--;
        }
        string left;
        int leftLen = -1;
        if (index1 >= 0) {
            left = num1;
            leftLen = index1;
        } else {
            left = num2;
            leftLen = index2;
        }
        while (leftLen >= 0) {
            int res = left[leftLen] - '0' + carry;
            carry = res / 10;
            int val = res % 10;
            //result = to_string(val) + result;
            result.insert(0, 1, val + '0');
            leftLen--;
        }
        if (carry > 0) {
            result.insert(0, 1, carry + '0');
            //result = to_string(carry) + result;
        }
        return result;
    }
};

Note

第一次提交的时候耗时和内存都惨不忍睹，看了别人题解做了一点改进，耗时和内存就优化了不少。要养成好的编码习惯，记住它：字符串拼接不要使用加号。
字符串和char的拼接，不要使用to_string(char) + string。
c++ string有push_back和insert方法来插入一个char，用这个来代替加号拼接。性能就能提高不少。

image.png

Ref

https://www.cnblogs.com/meihao1203/p/9670680.html
https://blog.csdn.net/ETalien_/article/details/88375315

解法2

class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int> vals(num1.size() + num2.size(), 0);
        for (int j = num2.size() - 1; j >= 0; j--) {
            for (int i = num1.size() - 1; i >= 0; i--) {
                int mul = (num2[j] - '0') * (num1[i] - '0');
                int sum = mul + vals[i+j+1];
                vals[i+j+1] = sum % 10;
                vals[i+j] += sum / 10;
            }
        }
        string res;
        int index = 0;
        for(; index < vals.size() && vals[index] == 0; index++);
        while (index < vals.size()) {
            res.push_back(vals[index] + '0');
            index++;
        }
        return (res.empty()) ? "0" : res;
    }
};

这种解法耗时就低多了，因为他巧啊，并不是暴力模拟手工乘法。但这需要另一种拆解乘法的方法。

image.png

1. 子问题拆解：从num1 num2尾部开始往前遍历，取对应字符转成int后相乘。拆成charchar而不是暴力方法charstring，这样更适合高效实现。
2. 发现规律：num1中index i乘以num2中index j的最终结果index在[i+j, i+j+1]范围，这样直接放在中间结果vector中的对应位置就好，不需要移动字符串了。