Decode Ways Medium 0 attempts
LeetCode ↗

Decode Ways

Medium Dynamic ProgrammingMemoization LeetCode

A string of digits can represent an encoded message where each letter A through Z maps to the numbers 1 through 26. Given such a digit string s, count all the different ways it could be decoded back into letters.

Input Format
Implement numDecodings(s). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
s = "12"
Output
2

Example 2

Input
s = "226"
Output
3

Example 3

Input
s = "06"
Output
0
Constraints
  • 1 <= s.length <= 100
  • s contains decimal digits
  • The number of decodings fits in a signed 32-bit integer.
Test Cases (3)
Case 1
Args: ["12"] Expected: 2
Case 2
Args: ["226"] Expected: 3
Case 3
Args: ["06"] Expected: 0
Topics
Dynamic ProgrammingMemoization

DP

javascript
function numDecodings(s) {
  if (s[0] === '0') return 0;
  const n = s.length;
  let prev2 = 1, prev1 = 1;
  for (let i = 1; i < n; i++) {
    let curr = 0;
    if (s[i] !== '0') curr += prev1;
    const two = parseInt(s.slice(i-1, i+1));
    if (two >= 10 && two <= 26) curr += prev2;
    prev2 = prev1; prev1 = curr;
  }
  return prev1;
}

Time: O(n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript