Isomorphic Strings
EasyPrompt
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 * 104t.length == s.lengthsandtconsist of any valid ascii character.
Approaches
3 approaches with complexity analysis and trade-offs.
Use two character arrays to store the mappings between characters of both strings. Iterate through both strings simultaneously and check if the mappings are consistent.
Algorithm
- Create two character arrays sToT and tToS of size 256
- Iterate through both strings simultaneously
- For each character pair:
- Check if sChar has a mapping in sToT
- If no mapping exists, create one
- If mapping exists, verify it matches tChar
- Repeat the same process for tChar in tToS
- Return true if all mappings are consistent
Walkthrough
This approach uses two character arrays of size 256 (for ASCII characters) to store the mappings from s to t and t to s. For each character in both strings, we check if there's already a mapping. If there is, we verify it matches the current characters. If there isn't, we create new mappings in both directions.
public boolean isIsomorphic(String s, String t) { char[] sToT = new char[256]; char[] tToS = new char[256]; for (int i = 0; i < s.length(); i++) { char sChar = s.charAt(i); char tChar = t.charAt(i); // Check mapping from s to t if (sToT[sChar] == 0) { sToT[sChar] = tChar; } else if (sToT[sChar] != tChar) { return false; } // Check mapping from t to s if (tToS[tChar] == 0) { tToS[tChar] = sChar; } else if (tToS[tChar] != sChar) { return false; } } return true;}Complexity
Time
O(n) where n is the length of the strings
Space
O(1) since we use fixed-size arrays of 256 characters
Trade-offs
Pros
Simple implementation
Easy to understand
Works with ASCII characters
Cons
Uses more space than necessary if strings only contain a small subset of ASCII characters
Not suitable for Unicode strings without modification
Solutions
Solution
public class Solution { public bool IsIsomorphic(string s, string t) { int[] d1 = new int[256]; int[] d2 = new int[256]; for (int i = 0; i < s.Length; ++i) { var a = s[i]; var b = t[i]; if (d1[a] != d2[b]) { return false; } d1[a] = i + 1; d2[b] = i + 1; } return true; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.