问题描述： 

以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。
数据范围： 读入的数字大小满足0≤n≤101000
要求：空间复杂度 O(n)，时间复杂度 O(n2)

问题分析：两个数相乘可以拆成较小的一个数的每位与较大的数乘积，然后每个乘积的和就是
两数相乘的结果。所以我们需要解决的问题就拆分成了1、1位数与一个大数相乘；2、两个大
数相加的问题。
两个大数相加，字符串形式比较简单，主要就是注意进位问题。
然后就是一个个位数与一个大数相乘的问题。因为不确定乘积是几位数，每次的乘积都不同，
所以我们可以将末尾放在前面然后逐个加到字符串后面，最后反转所得到的字符串。
大数相加具体过程看函数sadds()，个位数与大数相乘可以看函数Pro()；在需要注意的地方都
有相应的注释。代码中有个欲处理如果t的长度比s的长度大，那么就进行swap(s,t)操作，这样
是为了保证s在长度上是最大的，也能减少迭代次数，同时还能优化函数设计。
复杂度分析：假设s.size=m,t.size=n
时间复杂度O(n2)：Pro函数为O(n)，取决于m的大小；sadds()函数为O(n2)，取决于m*n的大小。
空间复杂度O(n2)：取决于m*n的大小。 
class Solution {
public:
    string solve(string s, string t) {
        if(s.size()<t.size()) swap(s,t);
        if(t[0]=='0') return "0";
        int N=t.size();
        int M=s.size();
        string curZero="";//保存当前需要在得数后面添加0的个数
        string res="";//保存答案
        string cur;//当前乘积，t中每个数与s的乘积。
        for(int i=N-1;i>=0;--i) {
            if(t[i]=='0') cur="0";
            else cur=Pro(s,M,t[i]-'0')+curZero;//每次需要在后面添加0
            res=sadds(res,cur);
            curZero+="0";
        }
        return res;
    }
    string sadds(string res,string str2) {
        if(str2=="0") return res;
        if(res.size()<str2.size()) swap(res,str2);//保证res是最大长度的
        int k=0;//进位标志
        int x;//保存两个字符串每位相加的和，需加进位。从底到高
        int m=res.size()-1;
        int n=str2.size()-1;
        while(n>=0) {
            x=res[m]-'0'+str2[n]-'0'+k;
            res[m]=(x%10)+'0';
            k=x/10;
            --m,--n;
        }
        if(m==n&&k) {//当两个字符串长度相等时，需要考虑最后一次的进位
            res.insert(res.begin(),'1');
            return res;
        }
        while(m>=0&&k) {//较短字符串已经结束了，每次就看是否有进位
            x=res[m]-'0'+k;
            res[m]=(x%10)+'0';
            k=x/10;
            --m;
        }
        //如果上面一步一直到第一位，就需要看是否有进位
        if(m==-1&&k) res.insert(res.begin(),'1');
        return res;
    }
    string Pro(string s,int M,int x) {
//        if(x==0) return "0";//主函数已经考虑了t[i]==‘0’
        string m="";//保存当前乘积，是倒着的，方便操作
        int k=0;//进位标
        int mul=0;//x就是主函数t[i]的数字，保存每次x与s[j]的乘积
        for(int j=M-1;j>=0;--j) {
            mul=(s[j]-'0')*x+k;
            m+=((mul%10)+'0');
            k=mul/10;
        }
        if(k!=0) m+=(k+'0');//结束后需要看是否有进位
        reverse(m.begin(),m.end());//最后反转字符串就是当前乘积
        return m;
    }
};