# 43. Multiply Strings LeetCode

## 43. 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.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

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

Example 2:

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

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.

### Solution

Idea:
We are using regular mathematical vertical multiplication.
We loop from the end of both numbers, multiply the digits one at a time and save the carry in the next cell for the next iteration.
The loop at the end constructs the result string - we skip 0s at the beginning and add the numbers.

Time Complexity: O(mn)
Space Complexity: O(n+m)

class Solution {
public:
string multiply(string num1string num2) {
if(num1=="0" || num2=="0"){
return "0";
}
vector<int>v(num1.size()+num2.size(),0);
for(int i=num1.size()-1i>=0i--){
for(int j=num2.size()-1j>=0j--){
v[i+j+1]+=(num1[i]-'0')*(num2[j]-'0');
v[i+j]+=v[i+j+1]/10;
v[i+j+1]%=10;
}
}
int i=0;
string ans="";
while(v[i]==0){
i++;
}
while(i<v.size()){
ans+=to_string(v[i]);
i++;
}
return ans;
}
};