题目：
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

链接：Multiply Strings
解法：大数乘法，即逐位相乘，保存于数组中，最后转换回字符串。时间O(n^3)

class Solution {
public:
    void reverse(string &str) {
        int l = str.length();
        for(int i = ; i < l / ; i++) {
            char c = str[i];
            str[i] = str[l - i - ];
            str[l - i - ] = c;
        }
    }

    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") return "0";
        string ans;
        int box[];
        memset(box, , sizeof(box));
        for (int i = num1.size() - ; i >= ; i--)
            for (int j = num2.size() - ; j >= ; j--) 
                box[(num1.size() - i) + (num2.size() - j)] += (num1[i] - '0') * (num2[j] - '0');
        for (int i = ; i < ; i++) {
            box[i + ] += box[i] / ;
            box[i] = box[i] % ;
            ans.push_back('0' + box[i]);
        }
        for (int i = ans.size() - ; i >= ; i--)  {
            if (ans[i] != '0') {
                ans = ans.substr(, i + );
                break;
            }
        }
        reverse(ans);
        return ans;
    }
};

Runtime: 53 ms