Decrypt String From Alphabet To Integer Mapping - Leetcode Solution

Problem Statement:

Given a string s formed by digits ('0' - '9') and '#' . We want to map s to English lowercase characters as follows:

Characters ('a' to 'i') are represented by ('1' to '9') respectively. Characters ('j' to 'z') are represented by ('10#' to '26#') respectively. Return the string formed after mapping.

It's guaranteed that a unique mapping will always exist.

Example 1:

Input: s = "10#11#12" Output: "jkab" Explanation: "10#11#12" -> "j" + "k" + "ab" -> "jkab"

Example 2:

Input: s = "1326#" Output: "acz"

Example 3:

Input: s = "25#" Output: "y"

Example 4:

Input: s = "1234567890" Output: "abcdefghij"

Solution:

To solve this problem, we can use a simple approach:

1. We will traverse the given string s from last to the first character.
2. We will maintain a stack to store the English characters.
3. If we encounter a '#' character, we will pop the top two elements from the stack and combine them to form the corresponding English character.
4. If we encounter a digit, we will convert it to the corresponding character and push it on the stack.

Algorithm:

1. Initialize a stack to store the English characters.
2. Initialize an empty string to store the result.
3. Traverse the string s from last to first character.
4. If the current character is '#' then pop the top two characters from the stack and combine them to form the corresponding English character and push it on the stack.
5. If the current character is a digit then convert it to the corresponding English character and push it on the stack.
6. At the end of the traversal, pop all the elements from the stack and append them to the result string.
7. Return the reversed result string.

Pseudo code:

1. Initialize a stack to store the English characters.
2. Initialize an empty string to store the result.
3. Traverse the string s from last to first character. for i = n - 1 to 0 if s[i] == '#' pop two elements from the stack and combine them to form the corresponding English character and push it on the stack else convert the current digit to the corresponding English character and push it on the stack end for
4. At the end of the traversal, pop all the elements from the stack and append them to the result string. while the stack is not empty pop the top element from the stack and append it to the result end while
5. Return the reversed result string.

Code:

def freqAlphabets(s): stack = [] n = len(s)

for i in range(n-1, -1, -1):
    if s[i] == '#':
        num = int(s[i-2:i])
        stack.append(chr(num + 96))
        i -= 2
    else:
        stack.append(chr(int(s[i]) + 96))

result = ""

while stack:
    result += stack.pop()

return result[::-1]

Complexity Analysis:

Time Complexity: O(n), where n is the length of the input string s.

Space Complexity: O(n), where n is the length of the input string s because we are using a stack to store the English characters.

1