C++ Solution to Multiply Strings


  • 0
    A

    This is very basic solution to multiply string problem.

    class Solution {
    public:
        
        string add(string num1, string num2){
            
            if(num2 == "0")
                return num1;
            if(num1 == "0")
                return num2;
            
            string ans = "";
            int l1 = num1.length();
            int l2 = num2.length();
            int i = l1 - 1;
            int j = l2 - 1;
            int c = 0;
            while(i>=0 && j>=0){
                int a = num1[i]-'0';
                int b = num2[j]-'0';
                int s = (a+b+c);
                ans += (s%10)+'0';
                c = (s/10);
                i--;j--;
            }
            
            while(i>=0){
                int a = num1[i]-'0';
                int s = (a+c);
                ans += (s%10)+'0';
                c = (s/10);
                i--;
            }
            
            while(j>=0){
                int b = num2[j]-'0';
                int s = (b+c);
                ans += (s%10)+'0';
                c = (s/10);
                j--;
            }
            
            if(ans.length()==0)
                return "0";
            if(c){
                ans += c + '0';
            }
            
            int k = ans.length();
            int j1 = k-1;
            while(j1>=0 && ans[j1]=='0'){
                j1--;
            }
            if(j1<0)
                return "0";
            string ret = "";
            for(int z = j1; z >=0; z--){
                ret += ans[z];
            }
            
            return ret;
        }
        
        string multiply(string num1, string num2) {
            int l1 = num1.length();
            int l2 = num2.length();
            string prevRes = "0";
            string icr = "";
            for(int i = l2-1; i >= 0; i--){
                int carry = 0;
                int n = num2[i]-'0';
                string currRes = icr;
                for(int j = l1-1; j >= 0; j--){
                    int m = num1[j]-'0';
                    int t = m*n+carry;
                    currRes = (char)((t%10)+'0')+currRes;
                    carry = t/10;
                }
                if(carry){
                    currRes = (char)((carry)+'0') + currRes;
                }
                icr = icr + "0";
                prevRes = add(currRes, prevRes);
            }
            
            int k = prevRes.length();
            int j = 0;
            while(j<k && prevRes[j]=='0'){
                j++;
            }
            if(j==k)
                return "0";
            string ret = "";
            for(int z = j; z < k; z++){
                ret += prevRes[z];
            }
            return ret;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.