## 91. Decode Ways

###### tags: `Dynamic Programming` `Medium`

>[91. Decode Ways](https://leetcode.com/problems/decode-ways/description/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

:::

<hr/>

### Sol
:::spoiler Code

:::

<hr/>

### 東
`dp(n)` = `s[n] is valid` && `dp(n-1)` + `s.slice(n-1, n+1) is valid` && `dp(n-2)`

dp(0) = 1             // 1
dp(1) = 2             // (1,1) (11)
dp(2) = 2 + 1  = 3     // (1, 1, 1)(11,1) (1, 11)
dp(3) = 0 + 2 = 2     // (1, 1, 10)(11, 10)
dp(4) = 2 + 0 = 2     // (1, 1, 10, 6) (11, 10, 6)

:::spoiler Code

// Time O(n) | Space O(n) - n is the length of input string
var numDecodings = function(s) {
    const dp = new Array(s.length).fill(0);
    if(isValidDecode(s[0])) {
        dp[0] = 1;
    }

    if(s.length === 1) return dp[0];

    if(dp[0] && isValidDecode(s[1])) dp[1]++;
    if(isValidDecode(s.slice(0, 2))) dp[1]++;

    for(let i = 2; i < s.length; i++) {
        if(isValidDecode(s[i])) {
            dp[i] += dp[i-1];
        }

        if(isValidDecode(s.slice(i - 1, i + 1))) {
            dp[i] += dp[i-2];
        }
    }

    return dp[s.length - 1];
};

function isValidDecode(s) {
    if(s[0] === "0") return false;
    if(Number(s) === 0 || Number(s) > 26) return false;
    return true;
}

:::

<hr/>

### Jessie

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

:::

<hr/>

### Haoyu

:::spoiler Code

Reference: https://leetcode.com/problems/decode-ways/solutions/4454037/97-43-easy-solution-with-explanation/

var numDecodings = function(s) {
    if (!s || s[0] === '0') {
        return 0;
    }

    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; ++i) {
        const oneDigit = parseInt(s[i - 1]);
        const twoDigits = parseInt(s.substring(i - 2, i));

        if (oneDigit !== 0) {
            dp[i] += dp[i - 1];
        }

        if (10 <= twoDigits && twoDigits <= 26) {
            dp[i] += dp[i - 2];
        }
    }

    return dp[n];
};

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::