# [C++]LeetCode: 69 Multiply Strings

2015-01-06

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Attention：

1. 如果结果中最高位为0，需要去掉前导0.

``` int i = k+1;
while(tmpres[i] == 0)i--;//去掉乘积的前导0```
2. 如果结果为0，需要处理。

` if(i < 0)return "0"; //注意乘积为0的特殊情况`

3. string对象的下标从0开始，最后一个字符的下标为size() - 1，下标超出范围会引起溢出错误；

4. 注意存储空间的确定，位数等。

AC Code:

```class Solution {
public:
&#160; &#160; string multiply(string num1, string num2) {
&#160; &#160; &#160; &#160; int len1 = num1.size();
&#160; &#160; &#160; &#160; int len2 = num2.size();
&#160; &#160; &#160; &#160; vector tmp(len1 + len2, 0);
&#160; &#160; &#160; &#160; int k = len1 + len2 - 2; //最低位即 (len1-1) * (len2-1），存储到tmp[0]
&#160; &#160; &#160; &#160;&#160;
&#160; &#160; &#160; &#160; for(int i = 0; i < len1; i++)
&#160; &#160; &#160; &#160; {
&#160; &#160; &#160; &#160; &#160; &#160; for(int j = 0; j < len2; j++)
&#160; &#160; &#160; &#160; &#160; &#160; {
&#160; &#160; &#160; &#160; &#160; &#160; &#160; &#160; tmp[k-i-j] += (num1[i]-&#39;0&#39;) * (num2[j]-&#39;0&#39;);
&#160; &#160; &#160; &#160; &#160; &#160; }
&#160; &#160; &#160; &#160; }
&#160; &#160; &#160; &#160;&#160;
&#160; &#160; &#160; &#160; //处理进位
&#160; &#160; &#160; &#160; int carryBit = 0;
&#160; &#160; &#160; &#160; for(int i = 0; i < len1 + len2; i++)
&#160; &#160; &#160; &#160; {
&#160; &#160; &#160; &#160; &#160; &#160; tmp[i] += carryBit;
&#160; &#160; &#160; &#160; &#160; &#160; carryBit = tmp[i]/10;
&#160; &#160; &#160; &#160; &#160; &#160; tmp[i] %= 10;
&#160; &#160; &#160; &#160; }
&#160; &#160; &#160; &#160;&#160;
&#160; &#160; &#160; &#160; int i = k + 1;
&#160; &#160; &#160; &#160; while(tmp[i] == 0) i--; &#160;//去除乘积前导0
&#160; &#160; &#160; &#160; if(i < 0) return "0"; &#160; &#160;//处理特殊情况乘积为0
&#160; &#160; &#160; &#160;&#160;
&#160; &#160; &#160; &#160; string ret;
&#160; &#160; &#160; &#160; for(;i >= 0; i--)
&#160; &#160; &#160; &#160; {
&#160; &#160; &#160; &#160; &#160; &#160; ret.push_back(tmp[i] + &#39;0&#39;);
&#160; &#160; &#160; &#160; }
&#160; &#160; &#160; &#160;&#160;
&#160; &#160; &#160; &#160; return ret;
&#160; &#160; }
};```

1. 分别求出向量 {ai} 和向量 {bj} 的离散傅里叶变换 {Ai} 和 {Bj}。
2. 将 {Ai} 和 {Bj} 逐项相乘得到向量 {Ck}。
3. 对 {Ck} 求离散傅里叶逆变换，得到的向量 {ck} 就是向量 {ai} 和向量 {bj} 的卷积。
4. 对的向量 {ck} 进行适当的进位就得到了大整数 a 和 b 的乘积 c。