[LeetCode] Multiply Strings

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.

思路：

做过Plus One，Add Binary等题后，这类按位运算的题就是一个葫芦里的药了。按照最原始的按位相乘，最后移位相加的法则来计算。

      3 2 1

x       4 3

_______

      9 6 3

1 2 8 4

_______

1 3 8 0 3

注意：

1. m位的数字乘以n位的数字的结果最大为m+n位：

999*99 < 1000*100 = 100000，最多为3+2 = 5位数。

2. 先将字符串逆序便于从最低位开始计算。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: string multiply(string num1, string num2) { if(num1.empty() || num2.empty()) return ""; reverse(num1.begin(),num1.end()); reverse(num2.begin(),num2.end()); string ret(num1.size()+num2.size(),'0'); for(int j=0; j<num2.size(); j++) { int carry = 0; int val = num2[j] - '0'; for(int i=0; i<num1.size(); i++) { carry += ((num1[i]-'0')*val + (ret[i+j]-'0')); ret[i+j] = carry%10 + '0'; carry /= 10; } if(carry!=0) ret[num1.size()+j] = carry + '0'; } reverse(ret.begin(),ret.end()); int count = 0; while(count<ret.size()-1 && ret[count]=='0') count++; ret.erase(0,count); return ret; } };

总结：

题目虽然不难。要完全写对也不容易。
1. 首先要注意num1[i] * num2[j]的结果应该加到ret[i+j]的位置上。
2. 其次要注意ln 17不能遗漏最高位的进位，由于此时ret中该位为0，所以只需要将carry转为字符即可。
3. 最容易遗漏的corner case是ln 22-24。如999*0 = 0000，此时需要去掉开始的0，但又需要保留最后一个0。