0043._Multiply_Strings.md

43. Multiply Strings

难度:Medium

刷题内容

原题连接

• https://leetcode.com/problems/multiply-strings/

内容描述

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"
Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

思路1 - 时间复杂度: O(n^2)- 空间复杂度: O(1)******

由于这里的数字比较大超过了long long的最大值，因此不能转成数字，所以这里我们模拟两个数字的乘法。把每一位记录在一个字符串中。

class Solution {
public:
    string multiply(string num1, string num2) {
                string ans;
        int d[120][120];
        memset(d,0,sizeof(d));
        for(int i = num2.size() - 1;i >= 0;--i)
        {
            int count1 = 0;
            for(int j = num1.size()- 1;j >= 0;--j)
            {
                int pro_ans = (num1[j] - '0') * (num2[i] - '0');
                d[num2.size() - 1 - i][num1.size() - j - 1] = pro_ans % 10 + count1;
                count1 = pro_ans / 10;
                if(d[num2.size() - 1 - i][num1.size() - j - 1] >= 10)
                {
                    count1++;
                    d[num2.size() - 1 - i][num1.size() - j - 1] %= 10;
                }
            }
            d[num2.size() - 1 - i][num1.size()] = count1;
        }
        int count1 = 0;
        for(int j = 0;j < num1.size() + num2.size();++j)
        {
            for(int i = 0;i <= num2.size();++i)
                if(j - i >= 0  && j - i <= num1.size())
                    count1 += d[i][j - i];
            ans.push_back(count1 % 10 + '0');
            count1 /= 10;
        }
        while(ans.length() > 1 && ans[ans.length() - 1] == '0')
            ans.pop_back();
        reverse(ans.begin(),ans.end());
        return ans;
    }
};