Tuesday, June 4, 2013

Leetcode: Multiply Strings in C++



Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
Solution:

string multiply(string num1, string num2) {
       int s1 = num1.size();
       int s2 = num2.size();
       string result(s1+s2+1, '0');
       std::reverse(num1.begin(),num1.end());
       std::reverse(num2.begin(),num2.end());
       int digit1 = 0;
       int carry = 0;
       for(int i =0;i<s1;i++)
       {
           digit1 = num1[i] - '0';
           carry = 0;
           for(int j=0;j<s2;j++)
           {
               int digit2 = num2[j] - '0';
               int exist = result[i+j] - '0';
               result[i+j] = (digit1*digit2+exist+carry)%10 + '0';
               carry = (digit1*digit2+exist+carry)/10;
           }
           if(carry>0)
           {
               result[i+s2] = carry+'0';
           }
       }
       std::reverse(result.begin(),result.end());
       int start = 0;
       while(result[start]=='0'&&start<result.size()) // skip leading '0'
       {
           start++;
       }
       if(start == result.size())
       return "0";
       else
       return result.substr(start);
    }

No comments:

Post a Comment