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.

Tags: math, string

字符串相乘，关键是模拟我们平时手算乘法时的过程。取出num2的每一位，乘以num1，再把之前得到的re向左移一位，再加上这个循环中的结果。所以我们需要实现两个函数multiplyNum（字符串乘以数字）和sum（两个字符串相加）。

num1或num2为零需要单独考虑，否则结果会出现类似0000的情况。

class Solution {
public:
    string multiply(string num1, string num2) {
        int i = 0;
        string re;
        if(num1 == "0" || num2 == "0"){
            return string("0");
        }
        while(i < num2.size()){
            int digit = num2[i++] - '0';
            string thisRe = multiplyNum(num1, digit);
            if(re.empty()){
                re = thisRe;
            }
            else{
                re.push_back('0');
                re = sum(re, thisRe);
            }
        }
        return re;
    }
    string multiplyNum(string num1, int n){
        string re;
        int carry = 0;
        for(string::iterator it = num1.end() - 1; it >= num1.begin(); it--){
            int digit = *it - '0';
            int thisRe = digit * n + carry;
            carry = 0;
            while(thisRe >= 10){
                thisRe -= 10;
                carry++;
            }
            re.insert(re.begin(), (char)(thisRe + '0'));
        }
        if(carry != 0){
            re.insert(re.begin(), (char)(carry + '0'));
        }
        return re;
    }
    string sum(string num1, string num2){
        int carry = 0;
        int i = num1.size() - 1;
        int j = num2.size() - 1;
        string re;
        while(i >= 0 || j >= 0){
            int a = i >= 0? num1[i--] - '0': 0;
            int b = j >= 0? num2[j--] - '0': 0;
            int sum = a + b + carry;
            carry = 0;
            while(sum >= 10){
                sum -= 10;
                carry++;
            }
            re.insert(re.begin(), (char)(sum + '0'));
        }
        if(carry > 0){
            re.insert(re.begin(), (char)(carry + '0'));
            carry = 0;
        }
        return re;
    }
};