Jobs

Interviews

Discussions

Isomorphic Strings #7 Most Asked

Easy

Yandex

3 views

Topics:

Strings

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"

Output: true

Explanation:

The strings s and t can be made identical by:

Mapping 'e' to 'a'.
Mapping 'g' to 'd'.

Example 2:

Input: s = "foo", t = "bar"

Output: false

Explanation:

The strings s and t can not be made identical as 'o' needs to be mapped to both 'a' and 'r'.

Example 3:

Input: s = "paper", t = "title"

Output: true

Constraints:

1 <= s.length <= 5 * 10⁴
t.length == s.length
s and t consist of any valid ascii character.

Try coding it in LeetCode

Isomorphic Strings #7 Most Asked

Easy

Yandex

3 views

Topics:

Strings

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"

Output: true

Explanation:

The strings s and t can be made identical by:

Mapping 'e' to 'a'.
Mapping 'g' to 'd'.

Example 2:

Input: s = "foo", t = "bar"

Output: false

Explanation:

The strings s and t can not be made identical as 'o' needs to be mapped to both 'a' and 'r'.

Example 3:

Input: s = "paper", t = "title"

Output: true

Constraints:

1 <= s.length <= 5 * 10⁴
t.length == s.length
s and t consist of any valid ascii character.

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:

Are the input strings `s` and `t` guaranteed to be of the same length?
Are the input strings `s` and `t` case-sensitive, or should I treat them as case-insensitive?
Can the input strings `s` and `t` be empty or null?
Can the input strings `s` and `t` contain Unicode characters, and if so, should I consider the full Unicode range?
If the strings are not isomorphic, what should the function return? Should I return `false`, throw an exception, or is there another expected value?

Brute Force Solution

Approach

The brute-force method for checking if two words are isomorphic is like trying every possible way to match the letters in the first word to letters in the second word. We explore all combinations and see if any of them work perfectly without breaking the rules of isomorphism.

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

Take the first letter of the first word and try matching it with every letter in the second word.
For each of those possible matches, take the second letter of the first word and again try matching it with every letter in the second word.
Continue this process for every letter in the first word, always checking if the current match is consistent with the previous matches.
For example, if you already matched 'A' in the first word to 'X' in the second word, you can only match other 'A's in the first word to 'X's in the second word.
Also, ensure that no two different letters in the first word map to the same letter in the second word.
If, after trying all the possibilities, you find even one way to match all the letters in the first word to letters in the second word without breaking any rules, then the words are isomorphic.
If you exhaust all possible matches and cannot find a single consistent mapping, then the words are not isomorphic.

Code Implementation

def is_isomorphic_brute_force(first_word, second_word):
    if len(first_word) != len(second_word):
        return False

    def find_isomorphism(index, mapping):
        if index == len(first_word):
            return True

        first_word_character = first_word[index]

        for second_word_character in set(second_word):
            # Attempt to extend the current mapping with the new character
            new_mapping = mapping.copy()

            # Check if first character is already mapped to different second character
            if first_word_character in new_mapping and new_mapping[first_word_character] != second_word_character:
                continue

            # Ensures no two characters map to the same character
            if first_word_character not in new_mapping and second_word_character in new_mapping.values():
                continue

            new_mapping[first_word_character] = second_word_character

            is_valid = True
            for i in range(index + 1):
                if first_word[i] in new_mapping:
                    if new_mapping[first_word[i]] != second_word[second_word.index(second_word_character)] and first_word[i] == first_word_character:
                        is_valid = False
                        break
                elif first_word[i] == first_word_character:
                    is_valid = False
                    break

            if is_valid:
                consistent = True
                for i in range(index):
                    if first_word[i] in new_mapping:
                        if first_word[index] in new_mapping and new_mapping[first_word[i]] == new_mapping[first_word[index]] and first_word[i] != first_word[index]:
                            consistent = False
                            break

                if consistent:
                    # Recursively try to map the next character
                    if find_isomorphism(index + 1, new_mapping):
                        return True

        return False

    # Start with an empty mapping.
    return find_isomorphism(0, {})

Big(O) Analysis

Time Complexity

O(m^n) – The brute-force approach explores all possible mappings of characters from the first string (length m) to characters in the second string (length n). For each of the 'm' characters in the first string, we potentially try to map it to each of the 'n' characters in the second string. This leads to a recursive exploration of possibilities. In the worst case, where no early exits are possible, the number of mappings to explore grows exponentially with the length of the first string. Therefore, the time complexity is approximately O(n^m), where 'n' is the number of possible characters to map to, and 'm' is the length of the string being mapped.

Space Complexity

O(N^N) – The brute-force approach explores all possible mappings between characters of the first string to characters of the second string. In the worst case, for each character in the first string, it tries all possible characters in the second string. This leads to a recursion tree where each level corresponds to a character in the first string, and at each level, we branch out to all possible character assignments from the second string. This necessitates storing the current mapping being explored at each level of the recursion, which grows exponentially. The maximum depth of the recursion would be N (where N is the length of the strings), and at each level, we could potentially store N possible mappings, leading to a space complexity proportional to N^N in the worst case, to track these mappings through recursive calls and backtracking.

Optimal Solution

Approach

The trick here is to check if a pattern between two strings is consistent. We can do this by tracking the relationships between characters in each string. If the relationships are not consistently one-to-one, the strings are not isomorphic.

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

Imagine you have two dictionaries, one for each string. These dictionaries will remember which character in the first string corresponds to which character in the second string, and vice versa.
Start comparing the characters from the first string to the second string, going one by one.
If you find a character in the first string that you haven't seen before, check if the corresponding character in the second string has also not been seen before. If both are new, make a note that these characters are now linked to each other in your dictionaries.
If you find a character in the first string that you have seen before, check if the corresponding character in the second string matches the character that you previously linked it to. If it doesn't, the strings are not isomorphic.
Do the same thing but in reverse. Check if the character from the second string has already been linked with a character from the first string. If there's no match or if the character has been seen but does not correspond to a prior record, the strings are not isomorphic.
If you get through all the characters and everything matches up, then the strings are isomorphic.

Code Implementation

def are_strings_isomorphic(string_one, string_two):
    string_one_to_string_two_map = {}
    string_two_to_string_one_map = {}

    if len(string_one) != len(string_two):
        return False

    for i in range(len(string_one)):
        character_one = string_one[i]
        character_two = string_two[i]

        # Check mapping from string_one to string_two
        if character_one not in string_one_to_string_two_map:
            # Ensure no existing mapping conflicts
            if character_two in string_two_to_string_one_map:
                return False
            string_one_to_string_two_map[character_one] = character_two
            string_two_to_string_one_map[character_two] = character_one

        else:
            # Verify existing mapping consistency
            if string_one_to_string_two_map[character_one] != character_two:
                return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each character in both strings once. For each character, it performs constant-time operations: dictionary lookups and insertions. Therefore, the time complexity is directly proportional to the length of the input string, n, resulting in O(n).

Space Complexity

O(1) – The provided solution utilizes two dictionaries to store character mappings between the two input strings. In the worst-case scenario, where all characters in both strings are unique, each dictionary will store a maximum of the number of unique characters present in the input strings. Since the number of possible unique characters is limited (e.g., ASCII or Unicode character set), the size of the dictionaries is bounded by a constant, independent of the input string length N. Therefore, the space complexity is O(1), representing constant auxiliary space.

Edge Cases

Case	How to Handle
Both input strings are null	Return true, as null strings can be considered isomorphic to each other.
One string is null, the other is not	Return false, as strings of different 'lengths' (null vs. non-null) cannot be isomorphic.
Both strings are empty	Return true, as empty strings are isomorphic.
Strings have different lengths	Return false immediately, as strings of different lengths cannot be isomorphic.
Strings have length 1	Return true, as single-character strings are always isomorphic to each other.
String s has repeating characters mapped to the same character in t	The mapping should maintain consistency; if a character in 's' maps to a character in 't', any other occurrence of that character in 's' should map to the same character in 't'.
String t has repeating characters that map to the same character in s	The reverse mapping should also maintain consistency; if a character in 't' maps to a character in 's', any other occurrence of that character in 't' should map to the same character in 's'.
Maximum string length with limited memory	The solution should be efficient in terms of memory usage as the strings can be very large, preventing stack overflow or exceeding memory limits by utilizing hash maps which have O(n) space complexity.

Both input strings are null

How to Handle:

Return true, as null strings can be considered isomorphic to each other.

One string is null, the other is not

How to Handle:

Return false, as strings of different 'lengths' (null vs. non-null) cannot be isomorphic.

Both strings are empty

How to Handle:

Return true, as empty strings are isomorphic.

Strings have different lengths

How to Handle:

Return false immediately, as strings of different lengths cannot be isomorphic.

Strings have length 1

How to Handle:

Return true, as single-character strings are always isomorphic to each other.

String s has repeating characters mapped to the same character in t

How to Handle:

The mapping should maintain consistency; if a character in 's' maps to a character in 't', any other occurrence of that character in 's' should map to the same character in 't'.

String t has repeating characters that map to the same character in s

How to Handle:

The reverse mapping should also maintain consistency; if a character in 't' maps to a character in 's', any other occurrence of that character in 't' should map to the same character in 's'.

Maximum string length with limited memory

How to Handle:

The solution should be efficient in terms of memory usage as the strings can be very large, preventing stack overflow or exceeding memory limits by utilizing hash maps which have O(n) space complexity.

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:

Are the input strings `s` and `t` guaranteed to be of the same length?
Are the input strings `s` and `t` case-sensitive, or should I treat them as case-insensitive?
Can the input strings `s` and `t` be empty or null?
Can the input strings `s` and `t` contain Unicode characters, and if so, should I consider the full Unicode range?
If the strings are not isomorphic, what should the function return? Should I return `false`, throw an exception, or is there another expected value?

Brute Force Solution

Approach

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

Take the first letter of the first word and try matching it with every letter in the second word.
For each of those possible matches, take the second letter of the first word and again try matching it with every letter in the second word.
Continue this process for every letter in the first word, always checking if the current match is consistent with the previous matches.
For example, if you already matched 'A' in the first word to 'X' in the second word, you can only match other 'A's in the first word to 'X's in the second word.
Also, ensure that no two different letters in the first word map to the same letter in the second word.
If, after trying all the possibilities, you find even one way to match all the letters in the first word to letters in the second word without breaking any rules, then the words are isomorphic.
If you exhaust all possible matches and cannot find a single consistent mapping, then the words are not isomorphic.

Code Implementation

def is_isomorphic_brute_force(first_word, second_word):
    if len(first_word) != len(second_word):
        return False

    def find_isomorphism(index, mapping):
        if index == len(first_word):
            return True

        first_word_character = first_word[index]

        for second_word_character in set(second_word):
            # Attempt to extend the current mapping with the new character
            new_mapping = mapping.copy()

            # Check if first character is already mapped to different second character
            if first_word_character in new_mapping and new_mapping[first_word_character] != second_word_character:
                continue

            # Ensures no two characters map to the same character
            if first_word_character not in new_mapping and second_word_character in new_mapping.values():
                continue

            new_mapping[first_word_character] = second_word_character

            is_valid = True
            for i in range(index + 1):
                if first_word[i] in new_mapping:
                    if new_mapping[first_word[i]] != second_word[second_word.index(second_word_character)] and first_word[i] == first_word_character:
                        is_valid = False
                        break
                elif first_word[i] == first_word_character:
                    is_valid = False
                    break

            if is_valid:
                consistent = True
                for i in range(index):
                    if first_word[i] in new_mapping:
                        if first_word[index] in new_mapping and new_mapping[first_word[i]] == new_mapping[first_word[index]] and first_word[i] != first_word[index]:
                            consistent = False
                            break

                if consistent:
                    # Recursively try to map the next character
                    if find_isomorphism(index + 1, new_mapping):
                        return True

        return False

    # Start with an empty mapping.
    return find_isomorphism(0, {})

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have two dictionaries, one for each string. These dictionaries will remember which character in the first string corresponds to which character in the second string, and vice versa.
Start comparing the characters from the first string to the second string, going one by one.
If you find a character in the first string that you haven't seen before, check if the corresponding character in the second string has also not been seen before. If both are new, make a note that these characters are now linked to each other in your dictionaries.
If you find a character in the first string that you have seen before, check if the corresponding character in the second string matches the character that you previously linked it to. If it doesn't, the strings are not isomorphic.
Do the same thing but in reverse. Check if the character from the second string has already been linked with a character from the first string. If there's no match or if the character has been seen but does not correspond to a prior record, the strings are not isomorphic.
If you get through all the characters and everything matches up, then the strings are isomorphic.

Code Implementation

def are_strings_isomorphic(string_one, string_two):
    string_one_to_string_two_map = {}
    string_two_to_string_one_map = {}

    if len(string_one) != len(string_two):
        return False

    for i in range(len(string_one)):
        character_one = string_one[i]
        character_two = string_two[i]

        # Check mapping from string_one to string_two
        if character_one not in string_one_to_string_two_map:
            # Ensure no existing mapping conflicts
            if character_two in string_two_to_string_one_map:
                return False
            string_one_to_string_two_map[character_one] = character_two
            string_two_to_string_one_map[character_two] = character_one

        else:
            # Verify existing mapping consistency
            if string_one_to_string_two_map[character_one] != character_two:
                return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both input strings are null	Return true, as null strings can be considered isomorphic to each other.
One string is null, the other is not	Return false, as strings of different 'lengths' (null vs. non-null) cannot be isomorphic.
Both strings are empty	Return true, as empty strings are isomorphic.
Strings have different lengths	Return false immediately, as strings of different lengths cannot be isomorphic.
Strings have length 1	Return true, as single-character strings are always isomorphic to each other.
String s has repeating characters mapped to the same character in t	The mapping should maintain consistency; if a character in 's' maps to a character in 't', any other occurrence of that character in 's' should map to the same character in 't'.
String t has repeating characters that map to the same character in s	The reverse mapping should also maintain consistency; if a character in 't' maps to a character in 's', any other occurrence of that character in 't' should map to the same character in 's'.
Maximum string length with limited memory	The solution should be efficient in terms of memory usage as the strings can be very large, preventing stack overflow or exceeding memory limits by utilizing hash maps which have O(n) space complexity.

Both input strings are null

How to Handle:

Return true, as null strings can be considered isomorphic to each other.

One string is null, the other is not

How to Handle:

Return false, as strings of different 'lengths' (null vs. non-null) cannot be isomorphic.

Both strings are empty

How to Handle:

Return true, as empty strings are isomorphic.

Strings have different lengths

How to Handle:

Return false immediately, as strings of different lengths cannot be isomorphic.

Strings have length 1

How to Handle:

Return true, as single-character strings are always isomorphic to each other.

String s has repeating characters mapped to the same character in t

How to Handle:

The mapping should maintain consistency; if a character in 's' maps to a character in 't', any other occurrence of that character in 's' should map to the same character in 't'.

String t has repeating characters that map to the same character in s

How to Handle:

The reverse mapping should also maintain consistency; if a character in 't' maps to a character in 's', any other occurrence of that character in 't' should map to the same character in 's'.

Maximum string length with limited memory

How to Handle:

0/0 Yandex questions completed

0/0 completed