91. Decode Ways

DFS + memo

T: O(2^n) => O(n)

S: O(n)

class Solution {
    
    public int numDecodings(String s) {

        return dfs(0, s, new Integer[s.length()+1]);
    }
    private int dfs(int i, String s, Integer[] memo) {
        // we are counting how many ways there are to decode the entire string. 
        // We only increase the count by 1 when the entire string is decoded (i.e. reached the end)
        if (i == s.length()) {  //base case => 成立就 1 way
            return 1;
        }
        if (s.charAt(i) == '0') {
            return 0;
        }
        if (memo[i] != null) {
            return memo[i];
        }
        // 這題就是有兩個分支, 一位 or 2位, 但要符合規則
        int way1 = dfs(i+1, s, memo); // 選多一位的分支
        int way2 = 0;
        // 2 digits, 不越界, 選多2位的分支
        if (i < s.length() -1 && Integer.parseInt(s.substring(i, i+2)) <= 26) {
            way2 = dfs(i+2, s, memo);
        }
        memo[i] = way1 + way2;
        return memo[i];
    }
}

/*
  12
  / \
1   12 
/
2

brute force
O(2^n)


06
/
x

   121 
   /\
 1   12 \
 /\      1  => so when to the end, there 1 way 
2  21 => but if over 26, it's x
/     => so when to the end, there 1 way 
1 => so when to the end, there 1 way

 can't start with 0

first digit
1-9

first digit 1 , secodn 0~9
            2 , second 0~6
            
so subproblem, because most to 26 , 是兩位數所以不是用一位, 就是兩位

[1] 21 =>  dp[i+1]
or 
[12] 1 =>. dp[i+2]
dp[i] = dp[i+1] + dp[i+2]

i+1 位的 ways + i+2 位的 ways





*/

DP

top down

O(n)

O(n)

class Solution {
    
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n+1];
        
        dp[n] = 1;
        
        // 已經有 n 所以從 n-1 開始做
        for (int i = n-1; i >= 0; i--) {
            if (s.charAt(i) != '0') {
                dp[i] = dp[i+1];            
                if (i < n -1 && Integer.parseInt(s.substring(i, i+2)) <= 26) {
                    dp[i] += dp[i+2];
                }
            }
        }
        return dp[0];
    }
}

buttom up DP

class Solution {
  public int numDecodings(String s) {
    int n = s.length();
    int dp[] = new int[n+1];
    
    //Make it the same as 1 char condition maybe makes more sense? 
    dp[0] = s.charAt(0) == '0' ? 0 : 1;
    //dp[0] = 1; // empty string (why...??)
    dp[1] = s.charAt(0) == '0' ? 0 : 1; // one char
    
    // 所以狀態不是從 2位 來就是從 1位來, 然後要考慮一些限制
    for(int i = 2; i <= n; i++) {
      int twoDigit = Integer.parseInt(s.substring(i-2, i));
      if(twoDigit >= 10 && twoDigit <= 26) {
        dp[i] += dp[i-2];
      }
      
     int oneDigit = Integer.parseInt(s.substring(i-1, i));

      if(oneDigit >= 1 && oneDigit <= 9) {
        dp[i] += dp[i-1];
      }
    }
    
    return dp[n];
  }
}

dp => buttom up, so dp[i] = dp[i -xx

dfs+memo => top down, so result = dfs(i+1)....

/*

        12
        /\
       1  12 => count++
      / 
     2 =>  count++
     
     226
     /  \
     2  22
    /\    \
    2 26  6
    /
    6
    
    06
    / \
   0x  06 x
   
   so when 
   one digits => i = [1 or 2] => [i+1 => can be 0~9]
   two digits => i + 1 = [1 or 2] , i+2:  i+1~i+2 <= 26
*/

new comment

```java
class Solution {
    public int numDecodings(String s) {
        Integer[] memo = new Integer[s.length()];
        return dfs(s, 0, memo);
    }
    private int dfs(String s, int index, Integer[] memo) {
        if (s.length() == index) {
            return 1;
        }
        // base case: end with '0' (current char is 0), every time only check 1 char (current index)
        if (s.charAt(index) == '0') { // check current index(first), ex: 10 -> check to current char is 0! return 0
            return 0;
        }
        if (memo[index] != null) {
            return memo[index];
        }
        // check 1 len
        int result = dfs(s, index + 1, memo);
        // has 2 len
        if (index + 1 < s.length() && Integer.parseInt(s.substring(index, index+2)) <= 26) {
            result += dfs(s, index + 2, memo);
        }
        
        return memo[index] = result;
    }
}

/**
T: O(n)
S: O(n)
關鍵: 1個字母或2個字母
case:
i+1
or i+2
how to avoid leading '0'? check ""current char"" is not '0'

226
/\ \
2 2 6
    to the end -> one way!

226
/\ 
2 26 


226
/ \
22 6 

226
/ 
226
x 


     

 */
```

use char

```java
class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n+1];
        dp[0] = s.charAt(0) == '0' ? 0 : 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;

        for (int i = 2; i <= n; i++) {
            if (s.charAt(i-2) != '0' && Integer.parseInt(s.substring(i-2, i)) <= 26) {
                dp[i] += dp[i-2]; 
            }
            if (s.charAt(i-1) != '0') {
                dp[i] += dp[i-1];
            }

        }
        return dp[n];
    }
}
```