You are given a string s formed by digits and '#'. We want to map s to English lowercase characters as follows:
'a' to 'i') are represented by ('1' to '9') respectively.'j' to 'z') are represented by ('10#' to '26#') respectively.Return the string formed after mapping.
The test cases are generated so that a unique mapping will always exist.
Example 1:
Input: s = "10#11#12" Output: "jkab" Explanation: "j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".
Example 2:
Input: s = "1326#" Output: "acz"
Constraints:
1 <= s.length <= 1000s consists of digits and the '#' letter.s will be a valid string such that mapping is always possible.Problem Overview: You receive a string where numbers represent letters: 1-9 map to a-i and 10#-26# map to j-z. The task is to decode the string and return the resulting alphabetic text. The main challenge is detecting when a number is part of a two-digit mapping followed by #.
Approach 1: Two Pointer Approach (Time: O(n), Space: O(1))
Scan the string from left to right while checking whether the current position begins a two-digit encoded pattern. If s[i+2] == '#', then the substring s[i:i+2] represents a number between 10 and 26. Convert that value to its corresponding character using ASCII arithmetic and move the pointer forward by three positions. Otherwise, treat the current single digit as a value between 1 and 9, convert it to a letter, and advance the pointer by one. This method works well because the encoding guarantees that two-digit values always include the # marker, making detection constant time. The algorithm processes each character at most once, giving O(n) time complexity with O(1) extra space besides the output string. This approach fits naturally when working with sequential scans over string problems.
Approach 2: Reverse Parsing Approach (Time: O(n), Space: O(1))
Instead of scanning forward, start from the end of the string and build the result in reverse. When the current character is #, read the previous two digits to form a number between 10 and 26. Convert it into the corresponding letter and move the pointer three steps backward. If the current character is a digit, it represents a single-digit mapping, so convert it directly and move back one step. Because the encoding marker # always appears after two-digit numbers, reverse parsing avoids lookahead checks and simplifies the logic. The runtime remains O(n) since every character is processed once, and the algorithm uses O(1) additional memory. This approach is a good example of efficient string parsing techniques.
Recommended for interviews: The forward two pointer approach is usually what interviewers expect. It clearly demonstrates that you recognize the # pattern and handle variable-length tokens in a single pass. Reverse parsing is equally efficient and sometimes simpler to implement, so mentioning it shows deeper understanding of string processing strategies.
This approach leverages a two-pointer system to parse the string. The primary idea is to iterate through the string from the start to the end, using a pointer. Whenever we encounter a digit, we first check if the next character is '#'. If it is, it implies that this is a two-digit number representing a letter from 'j' to 'z'. Otherwise, it's a single character mapping.
This solution uses a simple iteration over the string. It checks for a '#' character two positions away every time it processes a digit. If found, it processes as a two-digit number, otherwise as a single digit.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), for storing the output string.
In this approach, the string is traversed from the end to the start. This helps in directly processing two-digit characters whenever a '#' is encountered. We will decode the string backwards.
The C solution iterates backwards, which simplifies handling two-digit directives (numbers followed by '#'). Post processing, the result is reversed to obtain the correct order.
Time Complexity: O(n).
Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Two Pointer Approach | Time Complexity: O(n), where n is the length of the string. |
| Reverse Parsing Approach | Time Complexity: O(n). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointer Approach | O(n) | O(1) | Best general solution when scanning strings sequentially and detecting encoded patterns |
| Reverse Parsing Approach | O(n) | O(1) | Useful when backward parsing simplifies detection of multi-character tokens |
Decrypt String from Alphabet to Integer Mapping (Leetcode 1309) • Coding Interviews • 2,964 views views
Watch 9 more video solutions →Practice Decrypt String from Alphabet to Integer Mapping with our built-in code editor and test cases.
Practice on FleetCode