LeetCode: Multiply Strings

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.

---

The idea is to compute each digit of the final product iteratively.

C++ Code:

/*
 * func: multiply_string
 * goal: multiply two numbers represented by strings
 * @param num1: number 1
 * @param num2: number 2
 * return: the product
 */
string multiply_string(string num1, string num2){
    int num1_length = static_cast<int>(num1.length());
    int num2_length = static_cast<int>(num2.length());
    int ret_length = num1_length + num2_length;
    int offset = ret_length-1;
    
    string result(ret_length,'0');
    vector<int> num(ret_length, 0);
    
    for(int i = ret_length-1, carry = 0; i >= 0; --i){
        //Compute the current digit
        for(int j = std::max(0, i - num2_length); j < num1_length && i - 1 - j >= 0; ++j){
            num[i] += (num1[j]-'0') * (num2[i-1-j] - '0');
        }
        //Add carry digit from last sum
        num[i] += carry;
        //Re-calculate carry digit
        carry = num[i]/10;
        //push back result
        result[i] = num[i]%10 + '0';
        if(result[i] != '0')
            offset = i;
    }
    
    return string(result.begin() + offset, result.end());
}

Python Code:

# func: multiply two big integers represented by string
# @param num1: input integer 1
# @param num2: input integer 2
# @return: the product
def multiply_strings(num1, num2):
    #Reverse the string first to make it more straight forward
    num1 = num1[::-1]
    num2 = num2[::-1]
    num1_len = len(num1)
    num2_len = len(num2)
    ret_len = num1_len + num2_len

    ret = [0] * ret_len
    for i in xrange(num1_len):
        for j in xrange(num2_len):
            ret[i + j] += int(num1[i]) * int(num2[j])

    result = ''
    carry = 0
    #Construct the final result
    for i in xrange(ret_len):
        digit = (ret[i] + carry) % 10
        carry = (ret[i] + carry) / 10
        result = str(digit) + result

    i = 0
    while i < len(result) and result[i] == '0':
        i += 1

    if i == len(result):
        return '0'
    else:
        return result[i:]

Reference Link:

[leetcode] Multiply Strings | 大整数的字符串乘法| Lexi's ... http://leetcodenotes.wordpress.com/2013/10/20/leetcode-multiply-strings-%E5%A4%A7%E6%95%B4%E6%95%B0%E7%9A%84%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B9%98%E6%B3%95/