目录
1、题目2、思路、c++代码4、java代码
1、题目
给定两个以字符串形式表示的非负整数num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。
示例1:
输入:num1="2",num2=""输出:"6"
示例2:
输入:num1="12",num2=""输出:""
说明：
num1和num2的长度小于。num1和num2只包含数字0-9。num1和num2均不以零开头，除非是数字0本身。不能使用任何标准库的大数类型（比如BigInteger）或直接将输入转换为整数来处理。
2、思路
(字符串模拟）O(nm)O(n*m)O(nm)
普通竖式
以num1=12,num2=为例：我们遍历num2每一位与num1进行相乘，将每一步的结果进行累加，在这个过程如果相乘或者相加的结果大于等于10，我们都要去满10进位，如下图所示：
这样模拟普通竖式计算的方法较为复杂，我们可以考虑优化版的竖式计算。
优化竖式
其实在相乘或者相加计算过程的每一位，我们可以考虑先不去满10进位，等到计算完所有的相乘结果以后，最终将其加到一块，再去满10进位，最后的结果和普通竖式一样，但却可以大大简化我们的模拟过程。(如下图所示)
具体过程如下：
1、长度是n和长度是m的数字相乘，最多只有n+m位，为了方便计算，将num1和num2反向存储到A[]和B[]中，即位数低的在数组前面，且开一个大小是n+m的C[]存储计算后的答案。2、两个数相乘时，将A*B[j]的结果累加到C[i+j]中，最后C[i+j]表示i+j这个位数的值是C[i+j](如上图所示)、由于C[]数组中的某些位数字可能是大于等于10的，我们从0枚举到n+m-1，进行满10进位，将所有位的值全部变成个位数。4、最后将C[]数组反转输出。
细节：
最终得到的数组C[]的高位可能包含前导0，因此在反转之前要先去除高位前导0。
时间复杂度分析：O(nm)O(n*m)O(nm)，nnn和mmm分别是num1num1num1和num2num2num2的长度。
、c++代码
classSolution{public:stringmultiply(stringnum1,stringnum2){vectorintA,B;intn=num1.size(),m=num2.size();for(inti=n-1;i=0;i--)A.push_back(num1-0);//反向存贮for(inti=m-1;i=0;i--)B.push_back(num2-0);vectorintC(n+m);for(inti=0;in;i++)for(intj=0;jm;j++)C[i+j]+=A*B[j];intt=0;//存贮进位for(inti=0;iC.size();i++){t+=C;C=t%10;t/=10;}intk=C.size()-1;while(k0!C[k])k--;//去除前导0strings;while(k=0)s+=C[k--]+0;//反转turns;}};
4、java代码
classSolution{publicStringmultiply(Stringnum1,Stringnum2){intn=num1.length(),m=num2.length();int[]A=newint[n],B=newint[m];for(inti=n-1;i=0;i--)A[n-1-i]=num1.charAt(i)-0;for(inti=m-1;i=0;i--)B[m-1-i]=num2.charAt(i)-0;int[]C=newint[n+m];for(inti=0;in;i++)for(intj=0;jm;j++)C[i+j]+=A*B[j];intt=0;for(inti=0;iC.length;i++){t+=C;C=t%10;t/=10;}intk=C.length-1;while(k0C[k]==0)k--;StringBuildersb=newStringBuilder();while(k=0)sb.append((char)(C[k--]+0));turnsb.toString();}}
原题链接：4.字符串相乘
,