Isomorphic Strings
Statement
Given two strings, find whether the two strings are isomorphic to each other or not. Two strings are isomorphic if a fixed mapping exists from the characters of one string to the character of the other string.
For example, if there are two instances of the character “a” in the first string, both these instances should be converted to another character in the second string. A character can also be mapped from the first string to itself in the second string. The converted character should be the same in both positions of the second string, since there’s a fixed mapping of characters in the first string to the second string.
Two different characters cannot map to the same character. Furthermore, all instances of a character must be replaced with another character while protecting the order of characters.
Constraints
- Both strings consist of valid ASCII characters
- 0 ≤ length of string ≤ 10⁴
- The length of both strings is the same
Solution
"""
production algorithm
"""
from collections import defaultdict
class Solution:
def is_isomorphic(self, s1, s2):
"""
time complexity O(n)
space complexity O(1)
"""
n = len(s1)
hashmap1, hashmap2 = defaultdict(int), defaultdict(int)
for i in range(n):
hashmap1[s1[i]] += 1
hashmap2[s2[i]] += 1
if not hashmap1[s1[i]] == hashmap2[s2[i]]:
return False
return True"""
unit tests
"""
from unittest import TestCase
from algorithms.hashmaps.isomorphic_strings.solution import Solution
class SolutionTestCase(TestCase):
def test_is_isomorphic_fails(self):
# Given
s1 = "xmtdkjswqblefinxgcvp"
s2 = "xmtdkjswqblefQQQgcvp"
solution = Solution()
# When
actual = solution.is_isomorphic(s1, s2)
# Then
expected = False
self.assertEqual(actual, expected)
def test_is_isomorphic_succeeds(self):
# Given
s1 = "xmtdkjswqblefinxgcvp"
s2 = "xmtdkjswqblefinxgcvp"
solution = Solution()
# When
actual = solution.is_isomorphic(s1, s2)
# Then
expected = True
self.assertEqual(actual, expected)Strategy
Hash Maps.
Explanation
The algorithm creates two hash maps as counters of the characters of both strings. Then, the indexes of the length of both strings is iterated. For each iteration, the character count of both strings is incremented in their respective hash map with the character of the current index.
Since each character in the first string should map to a distinct character in the second string, then if the character count for some index is not equal, then it means that the two strings aren’t isomorphic. However, if at the end of iteration the character count of both strings was equal at each step, then the two strings are isomorphic.
Time Complexity
The time complexity of the algorithm is O(n), where n is the length of both strings.
Space Complexity
The characters of both strings consist of valid ASCII characters, which is a constant number of characters. Therefore, the auxiliary space complexity of the algorithm is O(1).
