Decode Ways | Problems

A message of digits can be decoded to letters (1=A, 2=B, ..., 26=Z). Given a string s of digits, return the number of ways to decode it.

Example: s = "226" → Output: 3 ("BZ", "VF", "BBF")

Sample Input

—

Sample Output

—

Constraints

1 <= s.length <= 100
s contains only digits and may contain leading zeros

Test Cases

Case 1

Args: ["12"] Expected: 2

Case 2

Args: ["226"] Expected: 3

Case 3

Args: ["06"] Expected: 0

Topics

Dynamic Programming Memoization

DP

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.