Leetcode – Decrypt String from Alphabet to Integer Mapping Solution

The problem “Decrypt String from Alphabet to Integer Mapping” from Leetcode is an interesting string manipulation challenge that tests one’s ability to understand mappings and use them for conversion. Though the problem itself is relatively simple, it provides opportunities to discuss various coding strategies, string handling in Python, and algorithmic optimization. This article will dive into the problem statement, different ways to approach it, as well as complexity analysis.

Table of Contents

1. Problem Description
2. Naive Approach
3. Improved String Iteration Approach
4. Dictionary Mapping Approach
5. String Reversal and Backtracking Approach
6. Testing and Validation
7. Time and Space Complexity
8. Conclusion

1. Problem Description

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

• Characters that represent a number between 1 and 9 map to themselves.
• '10#' maps to 'j', '11#' maps to 'k', and so on till '26#' maps to 'z'.

The task is to return the string after this mapping is applied.

Example

Input: s = "10#11#12"

Output: jkab

Explanation: “10#” translates to “j”, “11#” translates to “k”, “12” translates to “a” and “b”. Hence the output is “jkab”.

Constraints

• 1 <= s.length <= 1000
• s[i] only contains digits and '#'.

2. Naive Approach

The naive approach is to traverse the string, checking three characters at a time to see if it should be converted to a letter.

Algorithm

1. Initialize an empty result string.
2. Loop through the string.
3. Check three characters ahead.
4. Add the corresponding letter to the result.

Python Code

def freqAlphabets(s):
    result = ""
    i = 0
    while i < len(s):
        if i + 2 < len(s) and s[i + 2] == "#":
            result += chr(96 + int(s[i:i + 2]))
            i += 3
        else:
            result += chr(96 + int(s[i]))
            i += 1
    return result

3. Improved String Iteration Approach

This approach also involves iterating through the string but uses Python’s native string functions for better performance.

Algorithm

1. Initialize an empty result string.
2. Use string slicing and str.join() for conversion.

Python Code

def freqAlphabets(s):
    result = []
    i = 0
    while i < len(s):
        if i + 2 < len(s) and s[i + 2] == "#":
            result.append(chr(96 + int(s[i:i + 2])))
            i += 3
        else:
            result.append(chr(96 + int(s[i])))
            i += 1
    return ''.join(result)

4. Dictionary Mapping Approach

This approach involves creating a dictionary to store the mappings for quicker lookup.

Algorithm

1. Create a dictionary with mappings.
2. Iterate through the string and replace accordingly.

Python Code

def freqAlphabets(s):
    mapping = {str(i): chr(96 + i) for i in range(1, 27)}
    result = []
    i = 0
    while i < len(s):
        if i + 2 < len(s) and s[i + 2] == "#":
            result.append(mapping[s[i:i+2]])
            i += 3
        else:
            result.append(mapping[s[i]])
            i += 1
    return ''.join(result)

5. String Reversal and Backtracking Approach

Another way to solve this problem is to reverse the string and then decode it from the end to the start.

Algorithm

1. Reverse the string.
2. Decode the characters in reverse order.

Python Code

def freqAlphabets(s):
    result = []
    i = len(s) - 1
    while i >= 0:
        if s[i] == "#":
            result.append(chr(96 + int(s[i-2:i])))
            i -= 3
        else:
            result.append(chr(96 + int(s[i])))
            i -= 1
    return ''.join(result[::-1])

6. Testing and Validation

• Test with only single-digit mappings.
• Test with only double-digit mappings.
• Test with a mixture of single and double-digit mappings.
• Test with large strings to analyze performance.

7. Time and Space Complexity

1. Naive Approach:
   • Time Complexity: O(n)
   • Space Complexity: O(n)
2. Improved String Iteration Approach:
   • Time Complexity: O(n)
   • Space Complexity: O(n)
3. Dictionary Mapping Approach:
   • Time Complexity: O(n)
   • Space Complexity: O(1) (not counting the output)
4. String Reversal and Backtracking Approach:
   • Time Complexity: O(n)
   • Space Complexity: O(n)

8. Conclusion

The “Decrypt String from Alphabet to Integer Mapping” problem from Leetcode serves as a valuable practice exercise for learning string manipulation techniques in Python. Though the problem is relatively straightforward, there are multiple ways to tackle it. By understanding these different methods, one can get a deeper grasp of Python string operations, algorithm design, and efficiency considerations.