91. Decode Ways

tags: Dynamic Programming Medium

91. Decode Ways

Optimal Space & Time Complexity

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

Thoughts & Solutions

YC

Code

---

Sol

Code

---

東

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)

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;
}

---

Jessie

Code

---

Howard

Code

---

Haoyu

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

---

Live Coding

(name)

// write your code here