1309. Decrypt String from Alphabet to Integer Mapping

EasyString
Leetcode Link

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:

  1. We iterate over the string s starting from the beginning.
  2. 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.
  3. 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'.
  4. We continue this until the end of the string, appending each translated letter to a result list.
  5. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of these pictures shows the visit order of a depth-first search?

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:

  1. Define a helper function named get, which takes a string s 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 the chr function, aligning '1' with 'a', '2' with 'b', etc. The logic can be expressed by: chr(ord('a') + int(s) - 1).

  2. Initialize two variables, i and n, where i will be used to iterate over the string s and n holds the length of the string.

  3. Start a while loop that continues as long as i is smaller than n. This loop will process each character or pair of characters followed by a '#' one at a time.

  4. 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'.

  5. If the condition is true, append the letter obtained from the helper function get by passing the substring from i to i + 2. Then increment i by 3 to account for the two digits and the '#' we just processed.

  6. 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 position i. Increment i by 1 to move to the next character.

  7. After the loop exits, use the join method on an empty string to concatenate all the elements in the result list res. This provides us with the final decoded string.

  8. 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 and n to the length of the string (which is 8).
  • Check the i+2 position for a '#', which is true at i = 0. Use get('12') to map to 'l' and increment i by 3.
  • Now i is 3, and i+2 is '11#', so get('11') maps to 'k' and i becomes 6.
  • Finally, i is 6, and i+2 hits '10#', so get('10') maps to 'j' and i becomes 9, which breaks the loop.
  • The result list res has ['l', 'k', 'j'], which joins to ljk.

By following this process, the solution efficiently decodes the entire string into the format we need.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the minimum element can be found in:

Example Walkthrough

Let's apply the solution approach step-by-step on a smaller example input: "2#5".

  • We initialize i to 0 and n 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 and s[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.

  • 2nd iteration (i = 1):

    • Now i is 1. Again, we check if there is a '#' at position i+2. This time, i+2 is 3 and s[3] is '#', indicating a two-digit number followed by '#'.
    • We call get(s[1:1+2]), which means get('25'), translating to 'y' using our custom function.
    • Increment i by 3 to move past the two-digit number and the '#'.

  • The while loop exits as i (now 4) is not smaller than n.

  • 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
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫