DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

1 1

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).

SOLUTION:

class Solution:
    memo = {}

    def isCorrect(self, n):
        if n[0] == "0":
            return False
        return int(n) >= 1 and int(n) <= 26

    def numDecodingsRec(self, s):
        if len(s) == 0:
            return 1
        if len(s) == 1:
            if self.isCorrect(s):
                return 1
            else:
                return 0
        if s in self.memo:
            return self.memo[s]
        numWays = 0
        if self.isCorrect(s[:1]):
            numWays += self.numDecodingsRec(s[1:])
        if self.isCorrect(s[:2]):
            numWays += self.numDecodingsRec(s[2:])
        self.memo[s] = numWays
        return numWays

    def numDecodings(self, s: str) -> int:
        self.memo = {}
        return self.numDecodingsRec(s)
Enter fullscreen mode Exit fullscreen mode

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

AWS GenAI LIVE!

GenAI LIVE! is a dynamic live-streamed show exploring how AWS and our partners are helping organizations unlock real value with generative AI.

Tune in to the full event

DEV is partnering to bring live events to the community. Join us or dismiss this billboard if you're not interested. ❤️