43.Multiply Strings

這題我覺得比加法還要難一點, 無論是十進位還是二進位

這邊我們先了解到 兩個數相乘的長度 會小於等於 兩個數長度的和

舉個例 20 * 20 = 400, 總共三位數 ≤ 四位數

最大不會超過, 所以我們先製造一個陣列 兩個數長度和的陣列

接著, 我們挑一個數, 並且從這個數的index, 讓這個單一個數去對上另一個樹的全部數, 然後依序把他放到剛剛製造的陣列裡

最後檢查開頭為0的跟carry就行了

後面結尾要注意0的case, 倘若成出來是0, 代表在過路開頭0的時候就會檢查超界, 請直接回傳0

class Solution {
public:
    string multiply(string num1, string num2) {
        int n1 = num1.size();
        int n2 = num2.size();
        if(n1 == 0 || n2 == 0){
            return "0";
        }
        std::vector<int> result(n1 + n2, 0);
        int index1 = 0;
        int index2 = 0;
        for(int i = n1-1;i>= 0;i--){
            int carry = 0;
            int n1 = num1[i] -'0';
            index2 = 0;
            for(int j = n2 -1; j >= 0; j--){
                int n2 = num2[j] - '0';
                int sum = n1 * n2 + result[index1 + index2] + carry;
                carry = sum / 10;
                result[index1 + index2] = sum % 10;
                index2++;
            }
            if(carry> 0){
                result[index1 + index2] += carry;
            }
            index1++;
        }
        int i = result.size() - 1;
        while(i >= 0 && result[i] == 0){
            i--;
        }
        if(i == -1) return "0";
        string res = "";
        while( i >= 0) res += to_string(result[i--]);
        return res;
}
};