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 = "f11", t = "b23"
Output: false
Explanation:
The strings s and t can not be made identical as '1' needs to be mapped to both '2' and '3'.
Example 3:
Input: s = "paper", t = "title"
Output: true
Constraints:
- 1 <= s.length <= 5 * 104
- t.length == s.length
- s and t consist of any valid ascii character.
My Solution
One way to solve this problem is to reduce both strings to lexicographically smallest string that maintains the order of characters. What I mean is if I have a string like “egg”, I will reduce the string to “abb”. Isomorphic strings as they are defined in this problem always have the same reduced string pattern. To reduce the string, I will maintain a HashMap that maps characters to the smallest character available. I will iterate through the string and if the character is not currently in the HashMap, I will map that character to the smallest current character, add the character to the reduced string output and increment the smallest character. If the character is in the HashMap, or in other words we have seen it before, we just need to add the mapped character to the reduced string output. We do this for both strings s and t. Finally if both reduced strings are the same, we return true that they are isomorphic. If they are not the same we return false.
Time complexity would be O(n), where n is the length of both strings because we scan both strings once to generate the reduced strings and then comparing the strings for equality is O(n). Space complexity is also O(n) to maintain the reduced strings as well as the HashMap.
class Solution {
public boolean isIsomorphic(String s, String t) {
String str1 = reduce(s);
String str2 = reduce(t);
return str1.equals(str2);
}
public String reduce(String s) {
StringBuilder sb = new StringBuilder();
char curr = 'a';
Map<Character,Character> map = new HashMap<>();
for (char c : s.toCharArray()) {
if (!map.containsKey(c)) {
sb.append(curr);
map.put(c, curr);
curr++;
}
else {
sb.append(map.get(c));
}
}
return sb.toString();
}
}