Decode Ways

---

Decode Ways: A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

---

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

---

Example 3:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F"
because of the leading zero ("6" is different from "06").

---

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

---

Try this Problem on your own or check similar problems:

1. Count Number of Texts
2. Decode Ways II

Solution:

Java

public int numDecodings(String s) {
    char prev = 'X';
    int oneStepBefore = 1, twoStepsBefore = 0;
    for(int i = 0; i < s.length(); ++i){
        char current = s.charAt(i);
        int totalWays = current == '0' ? 0 : oneStepBefore;
        if((prev == '1') || (prev == '2' && current <= '6')){
            totalWays += twoStepsBefore;
        }
        prev = current;
        twoStepsBefore = oneStepBefore;
        oneStepBefore = totalWays;
    }

    return oneStepBefore;
}

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
  let prev = "X";
  let oneStepBefore = 1,
    twoStepsBefore = 0;
  for (let i = 0; i < s.length; ++i) {
    const current = s.charAt(i);
    let totalWays = current === "0" ? 0 : oneStepBefore;
    if (prev === "1" || (prev === "2" && current <= "6")) {
      totalWays += twoStepsBefore;
    }
    prev = current;
    twoStepsBefore = oneStepBefore;
    oneStepBefore = totalWays;
  }

  return oneStepBefore;
};

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        prev = 'X'
        oneStepBefore, twoStepsBefore = 1, 0
        for i in range(len(s)):
            current = s[i]
            totalWays = oneStepBefore if current != '0' else 0
            if (prev == '1') or (prev == '2' and current <= '6'):
                totalWays += twoStepsBefore
            prev = current
            twoStepsBefore = oneStepBefore
            oneStepBefore = totalWays
        return oneStepBefore

C++

class Solution {
public:
    int numDecodings(string s) {
         char prev = 'X';
        int oneStepBefore = 1, twoStepsBefore = 0;
        for (int i = 0; i < s.length(); ++i) {
            char current = s[i];
            int totalWays = current == '0' ? 0 : oneStepBefore;
            if ((prev == '1') || (prev == '2' && current <= '6')) {
                totalWays += twoStepsBefore;
            }
            prev = current;
            twoStepsBefore = oneStepBefore;
            oneStepBefore = totalWays;
        }
        return oneStepBefore;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

It might be not obvious on the first look but it's actually Fibonacci Sequence (same as we had for Climbing Stairs) with a twist. We still have the similar logic of handling oneStepBefore and twoStepsBefore, but this time we're not adding oneStepBefore to totalWays if the current char is 0, why can't we? Well 0 cannot form a valid mapping to character, so if we have something like XX0, we cannot break it down to XX and 0, our only hope is that the second X is 1 or 2. We also keep track of previous characters to check if we can combine with the current one (e.g. 2X or 1X) if we do that than we have to add twoStepsBefore ways of decoding to our totalWays. Note that for prev == '2' for the current we can only have 0..6 to form a valid decoding. Finally, we return oneStepBefore as it will be equal to totalWays in the last loop iteration.