[LeetCode] Multiply Strings_综合

[Problem]

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.

[Analysis]
大数乘法，不要忘了最后一个进位，注意删除前导0

[Solution]

class Solution {
      
public:
    // add num2 to num1, make sure num1 has enough space
    string reverseAdd(string num1, string num2){
      
        int len1 = num1.length();
        int len2 = num2.length();
        int carry = 0, i;
        for(i = 0; i < len1; ++i){
      
            int sum = 0;
            if(i < len2){
      
                sum = (num1[i]-'0') + (num2[i]-'0') + carry;
            }
            else{
      
                sum = (num1[i]-'0') + carry;
            }
            carry = sum / 10;
            sum = sum % 10;
            num1[i] = char(sum + '0');
        }
        if(carry > 0){
      
            num1[i] = char(carry + '0');
        }
        return num1;
    }
   
    // reverse and remove heading '0'
    string reverseAndRemove(string num){
      
        int len = num.length();
        int i = len - 1;
        string res = "";
   
        // remove heading '0'
        while(i >= 0 && num[i] == '0'){
      
            i--;
        }
   
        // all of them are '0's
        if(i < 0){
      
            res.append("0");
        }
        else{
      
            for(int j = i; j >= 0; --j){
      
                res.append(num.substr(j, 1));
            }
        }
        return res;
    }
   
    // multiply
    string multiply(string num1, string num2) {
      
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        string res = "", tmp = "";
        int len1 = num1.length();
        int len2 = num2.length();
   
        // initial
        for(int i = 0; i < len1+len2; ++i){
      
            res.append("0");
            tmp.append("0");
        }
   
        // multiply
        int i, j;
        for(i = len2-1; i >= 0; --i){
      
            // product of num1*num2[i]
            string tmpProduct = tmp;
   
            // process of num1*num2[i]
            int carry = 0;
            for(j = len1-1; j >= 0; --j){
      
                int product = (num2[i]-'0') * (num1[j]-'0') + carry;
                carry = product / 10;
                product = product % 10;
   
                // reverse set
                tmpProduct[(len2-1-i)+(len1-1-j)] = char(product + '0');
            }
   
            // be careful the remained carry
            if(carry > 0){
      
                tmpProduct[(len2-1-i)+(len1-1-j)] = char(carry + '0');
            }
   
            // add temp product to res
            // MIND the res and tmpProduct are reversed
            res = reverseAdd(res, tmpProduct);
        }
   
        // reverse resul and remove heading '0'
        return reverseAndRemove(res);
    }
};