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 num1, string num2) {

        if(num1=="0" || num2=="0"){

            return "0";

        }

     vector<int>v(num1.size()+num2.size(),0);

        for(int i=num1.size()-1; i>=0; i--){

            for(int j=num2.size()-1; j>=0; j--){

                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;

    }

};