# 91. Decode Ways

## DFS + memo

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

S: O(n)

```java
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)

```java
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

```java
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
```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
```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];
    }
}
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/91.-decode-ways.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.