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