43. Multiply Strings

1.問題

2.想法

• 提問

  • 確認題意: 將輸入的兩個字串轉為數字相乘並返回對應的字串

• function header, parameter

• test input

• 說明想法

  • 由於輸入的字串長度最常可能會到110, 即使用long也會overflow

  • 因此解題的思路是將輸入的兩個字串每個位數放到array中

    • 個位數是array的max length - 1, 因此0的地方可能是沒有值的 (填0)

    • 用一個grid儲存長除法的數字

      • 長度為2倍max length, 並用一個指標移動左右, 此指標在每次計算時reset

      • 記得要計算餘數,計算下一位時要加回餘數

    • Create 一個char array儲存回傳的值, 記得要讓array[length] = 0

      • 記得要計算餘數

    • Create一個string, 由指標的位置起算

string aResult = string(&aOutput[aWriteIndex]);

• 測試計算複雜度

3.程式碼

class Solution {
public:
    string multiply(string num1, string num2) {
        int aLen1 = num1.length();
        int aLen2 = num2.length();
        int aMaxLen = max(aLen1, aLen2);
        int aNum1[aMaxLen + 1];
        int aNum2[aMaxLen + 1];
        for (int i = 0; i < aMaxLen; i++) {
            aNum1[i] = 0;
            aNum2[i] = 0;
        }
        
        for (int i = 0; i < aLen1; i++) {
            aNum1[aMaxLen - 1 - i] = int(num1[aLen1 - 1 - i] - '0');
        }
        
        for (int i = 0; i < aLen2; i++) {
            aNum2[aMaxLen - 1 - i] = int(num2[aLen2 - 1 - i] - '0');
        }
        
        //grid
        int aGridWidth = aMaxLen * 2;
        int aGridHeight = aMaxLen * 2;
        int aGrid[aGridWidth][aGridHeight];
        for (int i = 0; i < aGridWidth; i++) {
            for (int j = 0; j < aGridHeight; j++) {
                aGrid[i][j] = 0;
            }
        }
        
        //caculate grid
        int aCarry = 0, aWriteIndex = 0;
        for (int aDigit2 = aMaxLen - 1; aDigit2 >= 0; aDigit2--) {
            aCarry = 0;
            aWriteIndex = aGridWidth - aMaxLen + aDigit2;
            for (int aDigit1 = aMaxLen - 1; aDigit1 >= 0; aDigit1--) {
                int aProduct = aNum1[aDigit1] * aNum2[aDigit2] + aCarry;
                aGrid[aWriteIndex--][aDigit2] = (aProduct % 10);
                aCarry = aProduct / 10;
            }
            
            while (aCarry % 10 != 0) {
                aGrid[aWriteIndex--][aDigit2] = (aCarry % 10);
                aCarry /= 10; 
            }
        }
        
        
        
        //caculate output
        char aOutput[aGridWidth + 1];
        aOutput[aGridWidth] = 0;
        aWriteIndex = aGridWidth - 1;
        for (int i = aGridWidth - 1; i >=0; i--) {
            int aSum = aCarry;
            for (int j = 0; j < aGridHeight; j++) {
                aSum += aGrid[i][j];
            }
            aOutput[aWriteIndex--] = char((aSum % 10) + '0');
            aCarry = (aSum / 10);
        }
        
        while (aCarry != 0) {
            aOutput[aWriteIndex--] = char((aCarry % 10) + '0');
            aCarry /= 10; 
        }
        
        //Prevent underflow.
        if (aWriteIndex < 0) { 
            aWriteIndex = 0; 
        }
        
        //Chop off the leading zeroes...
        while (aWriteIndex < (aGridWidth - 1) && aOutput[aWriteIndex] == '0') {
            aWriteIndex += 1;
        }
        
        //Inset by our chopped zeroes...
        string aResult = string(&aOutput[aWriteIndex]);
        
        return aResult;
    }
};