字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = “2”, num2 = “3”
输出: “6”

示例 2:

输入: num1 = “123”, num2 = “456”
输出: “56088”

说明：

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

思路

我们以289*785为例：

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1[0]=='0'||num2[0]=='0'){
            return "0";
        }
        int len1 = num1.size();
        int len2 = num2.size();
        string s;//用来存储所得的字符串
        int step = 0;//表示进位
        vector<int> v(len1 + len2 , 0);//来存储字符串相乘的并相加的结果
        int k=len1+len2-2;//k的取值如上图
        for(int i=0;i < len1; i++){
            for(int j=0;j < len2; j++){
                v[k-i-j]+=(num1[i]-'0')*(num2[j]-'0');//将所乘的结果都存入
            }
        }
        for(int i=0;i<=k+1;i++){//k+1为k位的进位
            v[i]+=step;
            step=v[i]/10;
            v[i]%=10;
        }
        if (v[k + 1] != 0){//如果v[k]有进位则进行尾插
  s.push_back(v[k + 1] + '0');
 }
     for(int i=k;i>=0;i--){
              s.push_back(v[i]+'0');
         }
        s.push_back('\0');//字符串最后的\0
        return s;
    }
};