Jobs

Interviews

Discussions

Decrypt String from Alphabet to Integer Mapping

Easy

Asked by:

49 views

Topics:

Strings

You are given a string s formed by digits 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.

The test cases are generated so that a unique mapping will always exist.

Example 1:

Input: s = "10#11#12"
Output: "jkab"
Explanation: "j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".

Example 2:

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

Constraints:

1 <= s.length <= 1000
s consists of digits and the '#' letter.
s will be a valid string such that mapping is always possible.

Try coding it in LeetCode

Decrypt String from Alphabet to Integer Mapping

Easy

Asked by:

49 views

Topics:

Strings

You are given a string s formed by digits 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.

The test cases are generated so that a unique mapping will always exist.

Example 1:

Input: s = "10#11#12"
Output: "jkab"
Explanation: "j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".

Example 2:

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

Constraints:

1 <= s.length <= 1000
s consists of digits and the '#' letter.
s will be a valid string such that mapping is always possible.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` contain characters other than digits and '#'? For example, can it contain letters or spaces?
What is the maximum length of the input string `s`?
Is it guaranteed that the input string `s` will always represent a valid mapping, or do I need to handle cases where no valid decryption exists?
If multiple possible decryptions exist, is any valid decryption acceptable, or is there a preferred one?
Is the input case sensitive or should I convert it to lower or upper case first?

Brute Force Solution

Approach

We're given a coded message where numbers represent letters. A brute force solution means we'll try out every possible way to decode the message by checking all combinations of single and double digit numbers, seeing which ones turn into valid letters.

Here's how the algorithm would work step-by-step:

Start at the beginning of the coded message.
First, try decoding the first number as a single letter.
Then, see if the first two numbers together can also form a letter (if they are '10' to '26' followed by a '#').
For each possibility (single-digit or double-digit decoding), write down the corresponding letter and move forward in the coded message.
Repeat the process for the remaining part of the coded message, always trying both the single-digit and, if possible, the double-digit decoding.
Keep going until you've decoded the entire message based on your initial choices.
Now, go back to the beginning and try a different first choice (single-digit or double-digit if the original choice was single).
Continue exploring every single possible combination of single and double-digit decodings until you have checked all possibilities.
If any of the decoded messages only contain valid letters based on the initial number-to-letter mappings, return that message as the correct answer.

Code Implementation

def decrypt_string_from_alphabet_to_integer_mapping(coded_string):
    def backtrack(index, current_string):
        # If we've reached the end of the coded string, we've found a valid decryption.
        if index == len(coded_string):
            return current_string

        # Try decoding a single digit.
        if coded_string[index].isdigit() and '1' <= coded_string[index] <= '9':
            digit = int(coded_string[index])
            letter = chr(ord('a') + digit - 1)
            result = backtrack(index + 1, current_string + letter)
            if result:
                return result

        # Try decoding a double digit if possible.
        if index + 2 < len(coded_string) and coded_string[index+2] == '#':
            double_digit = coded_string[index:index + 2]
            if double_digit.isdigit() and '10' <= double_digit <= '26':
                digit = int(double_digit)
                letter = chr(ord('a') + digit - 1)
                result = backtrack(index + 3, current_string + letter)
                if result:
                    return result

        return None

    return backtrack(0, "")

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible combinations of single-digit and double-digit decodings. For each position in the input string of length n, there are two choices: decode as a single digit or, if possible, as a double digit. This branching leads to a binary tree search where each level represents a position in the string. Thus, the total number of possible paths explored is proportional to 2 raised to the power of n, representing all combinations. Therefore, the time complexity is O(2^n).

Space Complexity

O(N) – The brute force approach explores all possible combinations of single and double-digit decodings, potentially leading to exponential time complexity. To keep track of the currently decoded message and manage the backtracking process, the algorithm implicitly uses a call stack due to recursion. In the worst-case scenario, where nearly every digit can be decoded either as a single or double digit, the depth of the recursion can reach N, where N is the length of the input string. Therefore, the space complexity is O(N) due to the recursion stack.

Optimal Solution

Approach

The goal is to convert a special code back into regular letters. The key idea is to work backward, checking for two-digit codes before single-digit codes to avoid mistakes.

Here's how the algorithm would work step-by-step:

Begin at the very end of the coded message.
Check if the last few characters form a two-digit code (ending with a '#').
If it's a two-digit code, translate it into the corresponding letter.
If it's not a two-digit code, translate the last single digit into its letter.
Move backwards, repeating the checks for two-digit and single-digit codes.
Keep doing this until you reach the beginning of the message.
Put all the letters together to reveal the secret message.

Code Implementation

def decrypt_string(coded_string):
    result = ''
    string_length = len(coded_string)
    current_index = string_length - 1

    while current_index >= 0:
        # Check for two-digit code ending with '#'
        if coded_string[current_index] == '#':

            two_digit_code = coded_string[current_index - 2:current_index]
            
            # Convert the two-digit code to an integer and then to its corresponding letter
            integer_value = int(two_digit_code)
            letter = chr(integer_value + ord('a') - 1)
            result = letter + result
            current_index -= 3

        else:
            # Translate single digit code.
            single_digit_code = coded_string[current_index]
            integer_value = int(single_digit_code)

            letter = chr(integer_value + ord('a') - 1)
            result = letter + result
            current_index -= 1

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string s of length n exactly once, from right to left. In each iteration, it checks if the last character is a '#'. If it is, it extracts a two-digit number; otherwise, it extracts a single-digit number. These extractions and corresponding character conversions are constant-time operations. Therefore, the time complexity is directly proportional to the length of the input string, resulting in O(n).

Space Complexity

O(N) – The algorithm constructs a new string by iteratively prepending decoded characters. In the worst-case scenario, where no two-digit codes are present, the algorithm will add N single characters to this result string. Thus, the auxiliary space required to store the decoded string grows linearly with the length of the input string, which we denote as N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input string	Return an empty string, as there's nothing to decrypt.
Null input string	Throw an IllegalArgumentException or return null, depending on the problem's specification.
String contains characters other than digits and '#'	Throw an IllegalArgumentException or return an error message indicating invalid input.
String ends with '#' but doesn't have a two-digit prefix	Handle it as a single digit, or as an illegal argument if you need to parse according to the full rule
String starts with '0'	Treat '0' the same as other single digits or throw exception indicating invalid mapping.
A two digit sequence '27#' or higher	Treat these as invalid inputs or error because mapping is only upto 26.
Very long string exceeding memory limits	Consider processing the string in chunks to avoid memory exhaustion.
Consecutive '#' characters, like '10#10##'	Parse from right to left or skip consecutive #'s.

Empty input string

How to Handle:

Return an empty string, as there's nothing to decrypt.

Null input string

How to Handle:

Throw an IllegalArgumentException or return null, depending on the problem's specification.

String contains characters other than digits and '#'

How to Handle:

Throw an IllegalArgumentException or return an error message indicating invalid input.

String ends with '#' but doesn't have a two-digit prefix

How to Handle:

Handle it as a single digit, or as an illegal argument if you need to parse according to the full rule

String starts with '0'

How to Handle:

Treat '0' the same as other single digits or throw exception indicating invalid mapping.

A two digit sequence '27#' or higher

How to Handle:

Treat these as invalid inputs or error because mapping is only upto 26.

Very long string exceeding memory limits

How to Handle:

Consider processing the string in chunks to avoid memory exhaustion.

Consecutive '#' characters, like '10#10##'

How to Handle:

Parse from right to left or skip consecutive #'s.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` contain characters other than digits and '#'? For example, can it contain letters or spaces?
What is the maximum length of the input string `s`?
Is it guaranteed that the input string `s` will always represent a valid mapping, or do I need to handle cases where no valid decryption exists?
If multiple possible decryptions exist, is any valid decryption acceptable, or is there a preferred one?
Is the input case sensitive or should I convert it to lower or upper case first?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the coded message.
First, try decoding the first number as a single letter.
Then, see if the first two numbers together can also form a letter (if they are '10' to '26' followed by a '#').
For each possibility (single-digit or double-digit decoding), write down the corresponding letter and move forward in the coded message.
Repeat the process for the remaining part of the coded message, always trying both the single-digit and, if possible, the double-digit decoding.
Keep going until you've decoded the entire message based on your initial choices.
Now, go back to the beginning and try a different first choice (single-digit or double-digit if the original choice was single).
Continue exploring every single possible combination of single and double-digit decodings until you have checked all possibilities.
If any of the decoded messages only contain valid letters based on the initial number-to-letter mappings, return that message as the correct answer.

Code Implementation

def decrypt_string_from_alphabet_to_integer_mapping(coded_string):
    def backtrack(index, current_string):
        # If we've reached the end of the coded string, we've found a valid decryption.
        if index == len(coded_string):
            return current_string

        # Try decoding a single digit.
        if coded_string[index].isdigit() and '1' <= coded_string[index] <= '9':
            digit = int(coded_string[index])
            letter = chr(ord('a') + digit - 1)
            result = backtrack(index + 1, current_string + letter)
            if result:
                return result

        # Try decoding a double digit if possible.
        if index + 2 < len(coded_string) and coded_string[index+2] == '#':
            double_digit = coded_string[index:index + 2]
            if double_digit.isdigit() and '10' <= double_digit <= '26':
                digit = int(double_digit)
                letter = chr(ord('a') + digit - 1)
                result = backtrack(index + 3, current_string + letter)
                if result:
                    return result

        return None

    return backtrack(0, "")

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The goal is to convert a special code back into regular letters. The key idea is to work backward, checking for two-digit codes before single-digit codes to avoid mistakes.

Here's how the algorithm would work step-by-step:

Begin at the very end of the coded message.
Check if the last few characters form a two-digit code (ending with a '#').
If it's a two-digit code, translate it into the corresponding letter.
If it's not a two-digit code, translate the last single digit into its letter.
Move backwards, repeating the checks for two-digit and single-digit codes.
Keep doing this until you reach the beginning of the message.
Put all the letters together to reveal the secret message.

Code Implementation

def decrypt_string(coded_string):
    result = ''
    string_length = len(coded_string)
    current_index = string_length - 1

    while current_index >= 0:
        # Check for two-digit code ending with '#'
        if coded_string[current_index] == '#':

            two_digit_code = coded_string[current_index - 2:current_index]
            
            # Convert the two-digit code to an integer and then to its corresponding letter
            integer_value = int(two_digit_code)
            letter = chr(integer_value + ord('a') - 1)
            result = letter + result
            current_index -= 3

        else:
            # Translate single digit code.
            single_digit_code = coded_string[current_index]
            integer_value = int(single_digit_code)

            letter = chr(integer_value + ord('a') - 1)
            result = letter + result
            current_index -= 1

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	Return an empty string, as there's nothing to decrypt.
Null input string	Throw an IllegalArgumentException or return null, depending on the problem's specification.
String contains characters other than digits and '#'	Throw an IllegalArgumentException or return an error message indicating invalid input.
String ends with '#' but doesn't have a two-digit prefix	Handle it as a single digit, or as an illegal argument if you need to parse according to the full rule
String starts with '0'	Treat '0' the same as other single digits or throw exception indicating invalid mapping.
A two digit sequence '27#' or higher	Treat these as invalid inputs or error because mapping is only upto 26.
Very long string exceeding memory limits	Consider processing the string in chunks to avoid memory exhaustion.
Consecutive '#' characters, like '10#10##'	Parse from right to left or skip consecutive #'s.

Empty input string

How to Handle:

Return an empty string, as there's nothing to decrypt.

Null input string

How to Handle:

Throw an IllegalArgumentException or return null, depending on the problem's specification.

String contains characters other than digits and '#'

How to Handle:

Throw an IllegalArgumentException or return an error message indicating invalid input.

String ends with '#' but doesn't have a two-digit prefix

How to Handle:

Handle it as a single digit, or as an illegal argument if you need to parse according to the full rule

String starts with '0'

How to Handle:

Treat '0' the same as other single digits or throw exception indicating invalid mapping.

A two digit sequence '27#' or higher

How to Handle:

Treat these as invalid inputs or error because mapping is only upto 26.

Very long string exceeding memory limits

How to Handle:

Consider processing the string in chunks to avoid memory exhaustion.

Consecutive '#' characters, like '10#10##'

How to Handle:

Parse from right to left or skip consecutive #'s.