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; } };
4/08/2014
Leetcode -- Multiply Strings
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment