字符串相乘（43）

43. 字符串相乘 - 力扣（LeetCode）

解法：

class Solution {
public:string multiply(string num1, string num2) {string res = "0";for (int i = 0; i < num2.size(); ++i) {string str = multiplyOneNum(num1, num2[num2.size() - 1 - i], i);res = add(res, str);}return res;}private :string add(const string & num1, const string & num2){string res;res.reserve(max(num1.size(), num2.size()) + 1);int idx1 = num1.size() - 1;int idx2 = num2.size() - 1;int carry = 0;while (idx1 >= 0 || idx2 >= 0 || carry > 0) {int num = 0;if (idx1 >= 0) {num += static_cast<int>(num1[idx1--] - '0');}if (idx2 >= 0) {num += static_cast<int>(num2[idx2--] - '0');}if (carry > 0) {num += carry;}carry = num / 10;num = num % 10;res.push_back(static_cast<char>(num + static_cast<int>('0')));}reverse(res.begin(), res.end());res.shrink_to_fit();return res;}string multiplyOneNum(const string & num1, const char & one_num , int times = 0){if (one_num == '0' || num1 == "0") {return "0";}string res;res.reserve(num1.size() + 1 + times);int carry = 0;for (int i = num1.size() - 1; i >= 0; --i) {int num = static_cast<int>(num1[i] - '0') * static_cast<int>(one_num - '0');if (carry > 0) {num += carry;}carry = num / 10;num = num % 10;res.push_back(static_cast<char>(num + static_cast<int>('0')));}if (carry) {res.push_back(static_cast<char>(carry + static_cast<int>('0')));}reverse(res.begin(), res.end());if (times > 0) {res.append(times, '0');}res.shrink_to_fit();return res;}
};

总结：

设num1的长度是m，num2的长度是n，multiplyOneNum函数的时间复杂度是O(m)， 由于result的长度是m + n，所以add函数的时间复杂度是O(m+n)，外面又一层循环n，所以时间的计算复杂度是O(mn) + O(mn + n2)，即O(mn + n2)。无论是 multiplyOneNum函数还是add函数最长使用的字符串长度是m+n，所以空间复杂度是O(m+n)。