43. Multiply Strings
1. Description
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
2. Note
You must not use any built-in BigInteger library or convert the inputs to integer directly.
3. Example
Example 1:
Input: num1 = “2”, num2 = “3”
Output: “6”
Example 2:
Input: num1 = “123”, num2 = “456”
Output: “56088”
4. Constraints
- 1 <= num1.length, num2.length <= 200
- num1 and num2 consist of digits only.
- Both num1 and num2 do not contain any leading zero, except the number 0 itself.
5. Solutions
My Accepted Solution(Follow Up)
m = i_num1.size(), n = i_num2.size()
Time complexity: O(mn)
Space complexity: O(1)
// imitate the process of multiply
class Solution
{
public:
string multiply(string &i_num1, string &i_num2)
{
if(i_num1 == "0" || i_num2 == "0") return string("0");
string result(i_num1.size() + i_num2.size(), '0');
for(int i = i_num1.size() - 1; i >= 0; i--)
{
int carry = 0;
for(int j = i_num2.size() - 1; j >= 0; j--)
{
int sum = (result[i + j + 1] - '0') + (i_num1[i] - '0')*(i_num2[j] - '0') + carry;
result[i + j + 1] = sum % 10 + '0';
carry = sum / 10;
}
// this digit doesn't care about the carry
// that's because the digit is a new digit, which is not existed before the process
// for example, 99 * 9, the result is 891, while '99' only have 2 digits
// so, for '8', it is a new digit, its most value is 9, which will not result in a carry as well
result[i] += carry;
}
return result.substr(result.find_first_not_of('0'));
}
};