1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
public:
    string multiply(string num1, string num2) {
        string ans = "";
        int inbit;
        // gen table
        vector<vector<int>> table;
        table.clear();
        for(int i = num1.length()-1; i >= 0; i--) {
            vector<int> item;
            item.clear(); 
            inbit = 0;
            for(int k = 0; k < num1.length()-1-i; k++)
                item.push_back(0);
            for(int j = num2.length()-1; j >= 0; j--) {
                int tmp = (num1[i] - '0') * (num2[j] - '0') + inbit;
                inbit = tmp / 10;
                item.push_back(tmp % 10);
            }
            if(inbit != 0)
                item.push_back(inbit);
            table.push_back(item);
        }
        // calc ansint
        vector<int> ansint;
        ansint.clear();
        int len = table[table.size()-1].size();
        inbit = 0;
        for(int i = 0; i < len; i++) {
            int tmp = inbit;
            for(int j = 0; j < table.size(); j++) {
                if(table[j].size() > i) {
                    tmp += table[j][i];
                }
            }
            inbit = tmp / 10;
            ansint.push_back(tmp % 10);
        }
        if(inbit != 0)
            ansint.push_back(inbit);
        bool flag = false;
        for(int i = ansint.size()-1; i >= 0; i--) {
            if(ansint[i] == 0 && i != 0 && flag == false) continue;
            ans.push_back(ansint[i] + '0');
            flag = true;
        }
        return ans;
    }
};