Thursday, October 10, 2013

Multiply Strings [Leetcode]

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: just math, but you may need to be very careful.

class Solution {
public:
    string multiply(string num1, string num2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(num1.empty() || num2.empty())
            return "";
        int s1 = num1.size();
        int s2 = num2.size();
        string ret(s1+s2, '0');
        int i, j;
        for(i=s1-1; i>=0; --i){
            int carry = 0;
            for(j=s2-1; j>=0; --j){
                int tmp = (ret[i+j+1]-'0')+(num1[i]-'0')*(num2[j]-'0')+carry;
                ret[i+j+1] = '0'+tmp%10;
                carry = tmp/10;
            }
            ret[i]+=carry;
        }
        //skip the leading 0's
        for(i=0; i<s1+s2; ++i){
            if(ret[i]!='0')
                return ret.substr(i, s1+s2-i);
        }
        return "0";
    }
};

No comments:

Post a Comment