91. Decode Ways - Medium

前往題目

想法

• 無，想說是不是可以用greedy

思路

DFS

1. 利用momization紀錄每個位置有幾種可能
2. 檢查一位數與二位數，並將結果加入cache

Time: O(n)
Space: O(n)

code實際執行會一直呼叫DFS方法直到最後一位，會return 1，這時才會開始return然後答案會慢慢建立起來，有一種從根源開始蔓延到最遠處，到底之後再帶著結果回來，還是一樣的繞…光是理解就花費心力，更別說自己想出來了…繼續練習

Code

從recursion到dp

// DFS
class Solution {
    public int numDecodings(String s) {
        Integer[] cache = new Integer[s.length()];
        return (s.length() == 0) ? 0 : dfs(0, s, cache);
    }

    private int dfs(int index, String s, Integer[] cache) {
        // Base cases
        // Check if reached the end
        if (index == s.length()) {
            return 1;
        }
        // Check bad case
        if (s.charAt(index) == '0') {
            return 0;
        }

        // Already exists
        if (cache[index] != null) return cache[index];

        // 1 digit
        int res = dfs(index + 1, s, cache);

        if ((index < s.length() - 1) && 
        ((s.charAt(index) == '1') ||
        (s.charAt(index) == '2' && s.charAt(index + 1) < '7'))) {
            // 2 digit
            res += dfs(index + 2, s, cache);
        }
        return cache[index] = res;
    }
}

2024/02/28

• 再做一次一樣霧煞煞…