Isomorphic Strings
Given two strings s and t, determine if they are isomorphic.
Two strings 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 = “ddg”, t = “ssv”
Output: true
Example 2:
Input: s = “tree”, t = “eref”
Output: false
Example 3:
Input: s = “xyzz”, t = “abcc”
Output: true
Note:
- You may assume both s and t have the same length.
Solution:
The idea is to map every character present in string s and t. Mapping is done using numbers. These numbers are mapped according to the in dex of the character like in example 3 given: x -> 1 and a -> 1. These will provide us the similarity of two characters present at an index of string s and t. So we take two arrays and mapping will be done through them. Since m1 and m2 are both initialized as 0, we want to use a new value when i == 0, so i + 1 works here. If any mapping values in both the arrays are different, that means they are not isomorphic and we return false. At the end, if the conditions are valid then we return true.
Implementation:
Java:
class Solution {
public:
bool isIsomorphic(string s, string t) {
int m1[256] = {0}, m2[256] = {0}, n = s.size();
for (int i = 0; i < n; ++i) {
if (m1[s[i]] != m2[t[i]]) return false;
m1[s[i]] = i + 1;
m2[t[i]] = i + 1;
}
return true;
}
};
Complexity Analysis:
Time Complexity: O(n)
Space Complexity: O(1).
