Ways to Decode
Updated
Problem statement
A message made of capital letters is encoded by replacing each letter with its position in the alphabet and joining the results with no separators: A becomes "1", B becomes "2", and so on up to Z, which becomes "26".
So each letter's code is exactly one of the strings "1" to "26". A piece such as "0", "06" or "27" is not the code of any letter.
Given the encoded string digits, return how many different messages encode to exactly digits. The count can be very large, so return it modulo 10^9 + 7. If no message encodes to digits, return 0.
Function
countDecodings(digits: String) → intExamples
Example 1
digits = "123"return = 3There are three ways to cut "123" into codes:
1,2,3givesABC.1,23givesAW.12,3givesLC.
Cutting off 123 as one piece is not possible because codes have at most two digits.
Example 2
digits = "2101"return = 1The 0 cannot stand alone, and 01 is not a code, so the 0 must be the end of the piece 10. That leaves 2 before it and 1 after it, so the only message is 2, 10, 1, which is BJA.
Example 3
digits = "301"return = 0The 0 cannot stand alone, 01 is not a code, and 30 is larger than 26. No cut puts the 0 inside a code, so no message encodes to this string.
Constraints
1 <= digits.length <= 10^4digitscontains only the characters0to9.
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Maximum Bouquet ValueOracle · ONSITE INTERVIEWOracle interview questions
- Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Word BreakGoogle · ONSITE INTERVIEWGoogle interview questions
- Reconstruct One Sentence From a DictionaryMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Scramble StringExpedia · ONSITE INTERVIEWExpedia interview questions
- Word BreakMoveworks · ONSITE INTERVIEWMoveworks interview questions
- Validate a Palindrome After Limited DeletionsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Decode Numeric StringArcesium · ONSITE INTERVIEWArcesium interview questions
- Word BreakBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Count Vowel PermutationsZscaler · ONSITE INTERVIEWZscaler interview questions