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�����ֵ����˲���ת�����֣内容描述�����ģ内容描述�ֵij˷�����ÿһλ��¼��һ���ַ����С�
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;
}
};
