Lecture 74 :- Isomorphic Strings

Two strings are considered isomorphic if they have the same pattern of character occurrences. In other words, you can replace characters in one string with other characters such that the two strings become identical. However, the mapping of characters should be one-to-one and onto, meaning each character in the first string should map to a unique character in the second string, and no two characters in the first string should map to the same character in the second string.

Here's a Python function to determine if two strings are isomorphic:

pythonCopy code
def is_isomorphic(s, t):
    if len(s) != len(t):
        return False

    char_mapping = {}
    used_chars = set()

    for i in range(len(s)):
        char_s, char_t = s[i], t[i]

        if char_s in char_mapping:
            if char_mapping[char_s] != char_t:
                return False
        else:
            if char_t in used_chars:
                return False
            char_mapping[char_s] = char_t
            used_chars.add(char_t)

    return True

# Example usage:
string1 = "egg"
string2 = "add"
print(is_isomorphic(string1, string2))  # Output: True

In this function, we first check if the lengths of the two input strings are equal. If they are not, they cannot be isomorphic, and we return False immediately.

We then use a dictionary, char_mapping, to store the mapping of characters from the first string to the second string. We also use a set, used_chars, to keep track of characters from the second string that have already been mapped to. For each character in the first string, we check if it is already in the char_mapping. If it is, we verify if the corresponding character in the second string matches the mapped character. If not, we return False. If the character is not in the mapping, we add it to the char_mapping and the used_chars set.

If the loop completes without returning False, it means that the two strings are isomorphic, and we return True.

The time complexity of this algorithm is O(N), where N is the length of the input strings, as we iterate through both strings once. The space complexity is also O(N) as we use dictionaries and sets to store mappings and used characters. 

Disclaimer: 

Copyright Disclaimer under Section 107 of the copyright act 1976, allowance is made for fair use fo purposes such as criticism, comment, news reporting, scholarship, and research. Fair use is a use permitted by copyright statute that might otherwise be infringing. Non-profit, educational or personal use tips the balance in favor of fair use.