1309. Decrypt String from Alphabet to Integer Mapping
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 77.8%
Problem Breakdown
The problem requires mapping a string s formed by digits ('0' - '9') and '#' characters into English lowercase letters. The mapping rules are:
- Characters
'a'to'i'are represented by'1'to'9'. - Characters
'j'to'z'are represented by'10#'to'26#'.
The task is to return the string formed after applying this mapping. The input string s will always be valid, ensuring a unique mapping exists.
Inputs:
- A string
scontaining digits and'#'.
Outputs:
- A string representing the mapped English lowercase letters.
Implicit Constraints/Edge Cases:
- The string length is between 1 and 1000.
- The input will always be valid, so no need to handle invalid inputs.
- No duplicates or negative numbers are involved.
- Overflow is not a concern due to the constraints.
Intuition
A brute-force approach would involve checking every possible substring of s for the presence of '#' and mapping accordingly. However, this would be inefficient in terms of both time and space complexity, especially given the string length constraint.
The key insight is to recognize that we can process the string from right to left. This allows us to handle the two-character mappings ('10#' to '26#') before processing single-digit mappings ('1' to '9'). By doing so, we ensure that each character or substring is processed only once.
Approach
- Initialize an empty list
resultto store the mapped characters. - Use a pointer
istarting from the end of the strings. - While
iis greater than or equal to 0:- If the current character
s[i]is'#', it indicates a two-character mapping:- Extract the substring
s[i-2:i](two characters before'#'). - Convert this substring to an integer and map it to the corresponding character.
- Append the character to
result. - Move the pointer
iback by 3 positions (i -= 3).
- Extract the substring
- Otherwise, it’s a single-digit mapping:
- Convert the current character
s[i]to an integer and map it to the corresponding character. - Append the character to
result. - Move the pointer
iback by 1 position (i -= 1).
- Convert the current character
- If the current character
- Reverse the
resultlist to get the correct order of characters. - Join the characters in
resultto form the final string and return it.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input string
s. Each character or substring is processed exactly once. - Space Complexity: O(n), for storing the result list, which can be as large as the input string.
Solution
def freqAlphabets(s: str) -> str:
result = []
i = len(s) - 1
while i >= 0:
if s[i] == '#':
# Two-character mapping
num = int(s[i-2:i])
result.append(chr(num + ord('a') - 1))
i -= 3
else:
# Single-digit mapping
num = int(s[i])
result.append(chr(num + ord('a') - 1))
i -= 1
return ''.join(result[::-1])
Edge Cases Handled
- Single-character mappings: The code correctly handles single-digit numbers by converting them to the corresponding characters.
- Two-character mappings: The code correctly identifies and processes substrings ending with
'#'to map them to the appropriate characters. - Mixed mappings: The code can handle strings that contain both single and two-character mappings, processing them in the correct order from right to left.