43. Multiply Strings - Medium

前往題目

思路

總之就是模擬乘法過程，不過其中的中繼的數字要放法怎麼放，要加上原本的還是不加…

1. 反轉兩個數字字符串
2. 以直式乘法來看的話，是動下面，再動上面，例如23 * 45，是先3 * 5再3 * 4。和平常反過來
3. 把結果放入陣列，兩個數字的位數加起來就是最多會有幾位
4. 反轉陣列，去掉leading zeros
5. 回傳答案

Code

class Solution {
    public String multiply(String num1, String num2) {
        // Base case
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        
        // 暫存陣列
        int[] res = new int[num1.length() + num2.length()];

        // 反轉字串
        num1 = reverseString(num1);
        num2 = reverseString(num2);

        // 走過每位數字
        for (int i = 0; i < num1.length(); i++) {
            for (int j = 0; j < num2.length(); j++) {
                // 位數相乘
                int digit = 
                    Integer.valueOf(String.valueOf(num1.charAt(i))) *
                    Integer.valueOf(String.valueOf(num2.charAt(j)));
                // 加入當前位置
                res[i + j] += digit;
                // 下一位放上當前數字的十位數
                res[i + j + 1] += res[i + j] / 10;
                // 當前位數只剩個位數
                res[i + j] = res[i + j] % 10;
            }
        }

        // 反轉陣列
        reverseArrayInPlace(res);

        // Avoid leading zeros
        int startIndex = 0;
        while (startIndex < res.length) {
            if (res[startIndex] != 0) break;
            ++startIndex;
        }

        // 產生答案
        StringBuilder buildResponse = new StringBuilder();
        for (int i = startIndex; i < res.length; i++) {
            buildResponse.append(res[i]);
        }

        return buildResponse.toString();
    }

    private String reverseString(String s) {
        StringBuilder reversedS = new StringBuilder(s);
        reversedS.reverse();
        return reversedS.toString();
    }

    private void reverseArrayInPlace(int[] arr) {
        for (int i = 0; i < arr.length / 2; i++) {
            int temp = arr[i];
            arr[i] = arr[arr.length - i - 1];
            arr[arr.length - i - 1] = temp;
        }
    }
}