1309. Decrypt String from Alphabet to Integer Mapping
Problem Description
The given problem defines a unique mapping system where digits are used to represent English lowercase letters, with some digits followed by a '#' symbol to represent letters beyond 'i'. Specifically, the digits '1' to '9' correspond to the letters 'a' to 'i', and the representation for letters 'j' to 'z' is given as two digits followed by a '#', starting with '10#' for 'j' and ending with '26#' for 'z'.
Given a string s
that is formed by these digits and '#' characters, the objective is to convert or map the string back to its English lowercase letter representation. For example, if the string s
is "10#11#12", the output should be "jk".
This mapping is bijective, meaning there will always be a unique solution to the mapping. One key detail stated in the problem is that test cases are generated in a way that ensures a unique mapping is always possible.
Intuition
To achieve the conversion from the given string s
to the lowercase English letters, we need to traverse the string and determine if we are dealing with a one-digit number (which maps to 'a' to 'i') or a two-digit number followed by a '#' (which maps to 'j' to 'z').
Our approach is as follows:
- We iterate over the string
s
starting from the beginning. - At each step, we check if there's a '#' character two positions ahead. If there is, it means the current and the next character form a two-digit number that corresponds to a letter from 'j' to 'z'. We then convert these two digits (and skip the '#' symbol) into the respective letter.
- If there's no '#' two positions ahead, we treat the current character as a one-digit number and convert it to the respective letter from 'a' to 'i'.
- We continue this until the end of the string, appending each translated letter to a result list.
- Once the traversal is done, we join all elements of the result list to form the final string.
This ensures that we are able to sequentially convert each number or number combination into its corresponding character, thereby obtaining the lowercased English letter representation of the input string.
Solution Approach
The solution's approach is rather straightforward and employs a simple while loop to iterate over the string. Let's walk through the implementation based on the provided Python code:
-
Define a helper function named
get
, which takes a strings
representing a number and converts it into a character. The function does this by first converting the string to an integer, then adding it to the ASCII value of 'a', and subtracting 1. This result is then converted back to a char using thechr
function, aligning '1' with 'a', '2' with 'b', etc. The logic can be expressed by:chr(ord('a') + int(s) - 1)
. -
Initialize two variables,
i
andn
, wherei
will be used to iterate over the strings
andn
holds the length of the string. -
Start a while loop that continues as long as
i
is smaller thann
. This loop will process each character or pair of characters followed by a '#' one at a time. -
Inside the loop, there's an if statement that checks if the current position
i
plus 2 is within bounds of the string and if there is a '#' character at this position. This condition confirms that we have a two-digit number that needs to be mapped to a character from 'j' to 'z'. -
If the condition is true, append the letter obtained from the helper function
get
by passing the substring fromi
toi + 2
. Then incrementi
by 3 to account for the two digits and the '#' we just processed. -
If the condition is false, it suggests we are currently handling a single digit. Append the result of the helper function
get
with the single character at positioni
. Incrementi
by 1 to move to the next character. -
After the loop exits, use the
join
method on an empty string to concatenate all the elements in the result listres
. This provides us with the final decoded string. -
Return the decoded string.
Notice how the solution ensures we correctly interpret characters that are either single-digit numbers or two-digit numbers followed by '#' without the need for separate parsing steps. The use of array slicing and the helper function makes the code more readable and maintainable.
Here's a step-by-step explanation of how the algorithm works on the input "12#11#10"
:
- Initialize
i
to 0 andn
to the length of the string (which is 8). - Check the
i+2
position for a '#', which is true ati = 0
. Useget('12')
to map to 'l' and incrementi
by 3. - Now
i
is 3, andi+2
is '11#', soget('11')
maps to 'k' andi
becomes 6. - Finally,
i
is 6, andi+2
hits '10#', soget('10')
maps to 'j' andi
becomes 9, which breaks the loop. - The result list
res
has ['l', 'k', 'j'], which joins toljk
.
By following this process, the solution efficiently decodes the entire string into the format we need.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's apply the solution approach step-by-step on a smaller example input: "2#5"
.
-
We initialize
i
to 0 andn
to 4, which is the length of the string. -
1st iteration (
i = 0
):- We check if there is a '#' at position
i+2
. However,i+2
is 2 ands[2]
is not '#', it's '5'. Therefore, we process a single-digit number. - We call
get('2')
, which translates to 'b' using our custom function. - Increment
i
by 1 to move to the next character.
- We check if there is a '#' at position
-
2nd iteration (
i = 1
):- Now
i
is 1. Again, we check if there is a '#' at positioni+2
. This time,i+2
is 3 ands[3]
is '#', indicating a two-digit number followed by '#'. - We call
get(s[1:1+2])
, which meansget('25')
, translating to 'y' using our custom function. - Increment
i
by 3 to move past the two-digit number and the '#'.
- Now
-
The while loop exits as
i
(now 4) is not smaller thann
. -
We finally join ['b', 'y'] to form the output string, resulting in
"by"
.
In this example, our first step was to convert the single digit '2' into 'b'. Then, we correctly identified '25#' as a representation of 'y' and completed our decoding process. The final result, for the input string "2#5"
, using the provided solution approach, is "by"
.
Solution Implementation
1class Solution:
2 def freqAlphabets(self, string: str) -> str:
3 # Helper function to convert a string number to its corresponding alphabet
4 def decode_to_char(s: str) -> str:
5 # The alphabet starts from 'a', hence the offset is 'a' + int(s) - 1
6 return chr(ord('a') + int(s) - 1)
7
8 # Initialize index and the length of the input string
9 index, length_of_string = 0, len(string)
10 # Initialize an empty list to store the resulting characters
11 result = []
12
13 # Iterate over the input string
14 while index < length_of_string:
15 # Check if a '#' follows two characters to detect if it's a two-digit number
16 if index + 2 < length_of_string and string[index + 2] == '#':
17 # If true, append the decoded character from the two-digit number to the result
18 result.append(decode_to_char(string[index: index + 2]))
19 # Move the index by 3 positions forward, skipping over the two digits and the '#'
20 index += 3
21 else:
22 # If false, it's a single-digit number which is directly appended after decoding
23 result.append(decode_to_char(string[index]))
24 # Move the index by 1 position forward
25 index += 1
26
27 # Join the list of characters into a string and return it
28 return ''.join(result)
29
1class Solution {
2
3 // Function to decode the string s as per the given pattern
4 public String freqAlphabets(String s) {
5 int index = 0; // Initialize index to keep track of the current position in the string
6 int strLength = s.length(); // Store the length of the input string for boundary checking
7 StringBuilder decodedString = new StringBuilder(); // StringBuilder to append the decoded characters
8
9 // Iterate through the string until all characters are processed
10 while (index < strLength) {
11 // Check if the current character is part of a two-digit number followed by a '#'
12 if (index + 2 < strLength && s.charAt(index + 2) == '#') {
13 // Decode the two-digit number and append the corresponding character
14 decodedString.append(decode(s.substring(index, index + 2)));
15 index += 3; // Skip the next two characters and the '#'
16 } else {
17 // Decode a single-digit number and append the corresponding character
18 decodedString.append(decode(s.substring(index, index + 1)));
19 index += 1; // Move to the next character
20 }
21 }
22
23 // Convert the StringBuilder to a String and return it
24 return decodedString.toString();
25 }
26
27 // Helper function to convert a numeric string to its respective alphabet character
28 private char decode(String numericString) {
29 // Subtract '1' because 'a' corresponds to '1', 'b' to '2', and so on.
30 // Parse the numeric string to an integer, subtract 1, and then add it to the char 'a'
31 return (char) ('a' + Integer.parseInt(numericString) - 1);
32 }
33
34}
35
1#include <iostream>
2#include <string>
3#include <vector>
4
5std::string freqAlphabets(const std::string& encoded_str) {
6 // Get the length of the input string.
7 size_t length = encoded_str.length();
8 // Initialize a vector to build the decoded characters.
9 std::vector<std::string> decoded_chars;
10 // Initialize an index to iterate over the input string.
11 size_t index = 0;
12
13 // Iterate over the input string.
14 while (index < length) {
15 // Check if there is a '#' two characters ahead.
16 if (index + 2 < length && encoded_str[index + 2] == '#') {
17 // If so, take the two characters before '#' and push them onto the vector.
18 decoded_chars.push_back(encoded_str.substr(index, 2));
19 // Skip the next two characters and the '#' by incrementing the index by 3.
20 index += 3;
21 } else {
22 // Otherwise, push the current character onto the vector.
23 decoded_chars.push_back(encoded_str.substr(index, 1));
24 // Move to the next character by incrementing the index by 1.
25 index++;
26 }
27 }
28
29 // Initialize the decoded string.
30 std::string decoded_str;
31
32 // Convert each encoded character or pair in the vector to the corresponding letter.
33 for (const auto& encoded_char : decoded_chars) {
34 // 'a' - 1 provides the offset necessary because 'a' starts at 97. Adding encoded_value gives us the ASCII value.
35 char decoded_char = static_cast<char>('a' + std::stoi(encoded_char) - 1);
36 // Add the decoded character to the decoded string.
37 decoded_str += decoded_char;
38 }
39
40 // Return the final decoded string.
41 return decoded_str;
42}
43
44// Example of using the function.
45int main() {
46 std::string encoded_string = "12#14#3#";
47 std::string decoded = freqAlphabets(encoded_string);
48 std::cout << "Decoded string: " << decoded << std::endl;
49 return 0;
50}
51
1function freqAlphabets(encodedStr: string): string {
2 // Get the length of the input string.
3 const length = encodedStr.length;
4 // Initialize an array to build the decoded characters.
5 const decodedChars: string[] = [];
6 // Initialize an index to iterate over the input string.
7 let index = 0;
8
9 // Iterate over the input string.
10 while (index < length) {
11 // Check if there is a '#' two characters ahead.
12 if (encodedStr[index + 2] === '#') {
13 // If so, slice the two characters before '#' and add them to the array.
14 decodedChars.push(encodedStr.slice(index, index + 2));
15 // Skip the next two characters and the '#' by incrementing the index by 3.
16 index += 3;
17 } else {
18 // Otherwise, add the current character to the array as is.
19 decodedChars.push(encodedStr[index]);
20 // Move to the next character by incrementing the index by 1.
21 index += 1;
22 }
23 }
24
25 // Map each character or pair in the array to its corresponding decoded character.
26 // Convert each encoded character to its respective letter in the alphabet.
27 return decodedChars.map(encodedChar =>
28 String.fromCharCode('a'.charCodeAt(0) + Number(encodedChar) - 1)
29 ).join(''); // Join the array of characters to form the final decoded string.
30}
31
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be analyzed by looking at the number of iterations it makes over the string s
. The code uses a while loop to iterate over each character of the string. The key operation within the loop is checking whether the next character is a special '#' and then either taking one or two characters to convert them into a letter. These operations are all constant time, and since the loop runs for each character or pair of characters marked with a '#', the time complexity is O(n)
, where n
is the length of the string s
.
Space Complexity
The code uses additional memory for the res
list to store the result. In the worst case, where there are no '#' characters, the res
list would have as many characters as the original string s
. Therefore, the space complexity is also O(n)
, where n
is the length of the string s
. In the case of the given code, the space complexity does not grow more than O(n)
as we are only creating a result list that, at most, will have the same length as the input.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time