4/08/2014

Leetcode -- Multiply Strings

class Solution {  
   public:  
   string multiply(string num1, string num2) {  
     string result;  
     int j = 0;  
     for(int i = num2.length() - 1; i >= 0 ; --i,j++) {  
       string sResult = singleMultiply(num1, num2[i] - '0');  
       for(int p =0; p < j; p++) {  
        sResult +='0';  
       }  
       result = add(result, sResult );  
     }  
        while(result[0] == '0' && result.length() > 1) {  
      result = result.substr(1);  
     }   
     return result;  
   }  
   string singleMultiply(string num1, int n2) {  
     int carry = 0;  
     list<char> result;  
     for(int i = num1.length() - 1; i >= 0; --i) {  
       int num = (num1[i] - '0') * n2 + carry;  
       int res = num % 10;  
       carry = num / 10;  
       result.emplace_front(res + '0');  
     }  
     if(carry) {  
       result.emplace_front(carry + '0');  
     }  
     string ret(result.begin(), result.end());  
     return ret;  
   }  
   string add(const string& num1, const string& num2) {  
     if(num1.length() < num2.length()) {  
       return add(num2, num1);  
     }  
     list<char> result;  
     int carry = 0;  
     int j = num1.length() - 1;  
     for(int i =num2.length() - 1; i >=0; --i, --j) {  
       int sum = num2[i] -'0' + num1[j]-'0' + carry;  
       int res = sum % 10;  
       carry = sum /10;  
       result.emplace_front(res + '0');  
     }  
     for(; j >=0; --j) {  
       int sum = num1[j]-'0' + carry;  
       int res = sum % 10;  
       carry = sum /10;  
       result.emplace_front(res + '0');  
     }  
     if(carry) {  
       result.emplace_front(carry + '0');  
     }  
     string ret(result.begin(), result.end());  
     return ret;  
   }  
 };  

No comments: