43. Multiply Strings LeetCode

 43Multiply 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;
    }
};

Post a Comment

0 Comments