问题传送门
解决思路
这个代码实现的思路就是简单的小学加减法：
999 * 999 = 999 * 9 + 999 * 90 + 999 * 900 = 999 * 9 + 999 * 9 * 10 + 999 * 9 * 100。
从中我们可以看出，乘法问题拆分成了两个子问题：
1、大数与一位数的乘法问题
2、大数之间的加法
代码
class Solution {
public:string addtion(string num1, string num2) {if(num1.size() < num2.size())swap(num1, num2);int i = num1.size() - 1, j = num2.size() - 1, carry = 0;for(; i >= 0 && j >= 0; --i, --j) {int sum = num1[i] + num2[j] + carry - 2 * '0' ;carry = sum / 10;num1[i] = sum % 10 + '0';}for(; i >= 0 && carry == 1; --i) {int sum = num1[i] + carry - '0' ;carry = sum / 10;num1[i] = sum % 10 + '0';}return carry ? '1' + num1 : num1;}string multiplyByOneChar(string num, char n) {int i = num.size() - 1, carry = 0;if(n == '0')return "0";for(; i >= 0; --i) {int mul = (num[i] - '0') * (n - '0');num[i] = (mul + carry) % 10 + '0';carry = (mul + carry) / 10;}return carry ? (char)(carry + '0') + num : num;}string multiply(string num1, string num2) {if(num1.size() > num2.size())swap(num1, num2);string result = "0";vector<string> mutCache(10, "");for(int i = 0; i < num1.size(); ++i) {string mul;if(mutCache[num1[num1.size() - 1 - i] - '0'] == "") {mul = multiplyByOneChar(num2, num1[num1.size() - 1 - i]);mutCache[num1[num1.size() - 1 - i] - '0'] = mul;}else {mul = mutCache[num1[num1.size() - 1 - i] - '0'];}if(mul != "0")mul += string(i, '0');result = addtion(result, mul);}return result;}
};