字符串乘法

基本思路：

1. 首先开辟一个长度为num1.size()+num2.size()的由0填充的新字符串
2. 然后从num2的尾部向头部遍历，每次遍历都与num1求和，将结果保存到新字符串中
3. 去除新字符串的前缀0，即为最终结果

代码如下：

//
// Created by jt on 2020/9/29.
//
#include <string>
using namespace std;

class Solution {
public:
    /**
     *
     * @param num1 string字符串
     * @param num2 string字符串
     * @return string字符串
     */
    string multiply(string num1, string num2) {
        // write code here
        string res = string(num1.size() + num2.size(), '0');
        int idx = num1.size()+num2.size()-1;
        for (int i = num2.size()-1; i >= 0; --i) {
            // offset保存res当前元素离末尾元素的偏移量，carry保存进位
            int offset, carry = 0, digit = num2[i] - '0';
            for (int j = num1.size()-1; j >= 0; --j) {
                offset = (num1.size()-1-j)+(num2.size()-1-i);
                int a = digit * (num1[j]-'0') + carry + res[idx-offset]-'0';
                res[idx-offset] = a % 10 + '0';
                carry = a / 10;
            }
            if (carry != 0) res[idx-offset-1] = carry + '0';
        }
        int begin = 0;
        while(begin < res.size() && res[begin] == '0') ++begin;
        if (begin == res.size()) return "0";
        else return res.substr(begin);
    }
};