# 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 = "egg", t = "add"
Output: true
``````

Example 2:

``````Input: s = "foo", t = "bar"
Output: false
``````

Example 3:

``````Input: s = "paper", t = "title"
Output: true
``````

Note:
You may assume boths andt have the same length.

## Analysis

#### Map to Index

@grandyang

The idea is that we need to map a char to another one, for example, "egg" and "add", we need to constract the mapping 'e' -> 'a' and 'g' -> 'd'. Instead of directly mapping 'e' to 'a', another way is to mark them with same value, for example, 'e' -> 1, 'a'-> 1, and 'g' -> 2, 'd' -> 2, this works same.

So we use two arrays here m1 and m2, initialized space is 256 (Since the whole ASCII size is 256, 128 also works here). Traverse the character of both s and t on the same position, if their mapping values in m1 and m2 are different, means they are not mapping correctly, returen false; else we construct the mapping, since m1 and m2 are both initialized as 0, we want to use a new value when i == 0, so i + 1 works here.

10 ms 77.19%

``````class Solution {
public boolean isIsomorphic(String s, String t) {
if (s.length() != t.length())
return false;

int[] sarr = new int[256];
int[] tarr = new int[256];
Arrays.fill(sarr, -1);
Arrays.fill(tarr, -1);

for (int i = 0; i < s.length(); i++) {
if (sarr[s.charAt(i)] != tarr[t.charAt(i)])
return false;
sarr[s.charAt(i)] = i;
tarr[t.charAt(i)] = i;
}

return true;
}
}
``````

#### Map between Character

HashMap + HashSet

HashMap存s -> t中字符映射关系

HashSet 检测是否有重复mapping，即 'a' -> 'b', 'b' -> 'b'这样的情形

25 ms, faster than 31.37%

``````public boolean isIsomorphic(String s, String t) {
if (s.length != t.length()) {
return false;
}
Map<Character,Character> map=new HashMap<>();
Set<Character> set=new HashSet<>();

for (int i = 0;i < s.length(); i++){
if (map.containsKey(s.charAt(i))){
if (map.get(s.charAt(i)) != t.charAt(i)) {
return false;
}
} else {
if (set.contains(t.charAt(i))) {
return false;
}
map.put(s.charAt(i), t.charAt(i));
}
}
return true;
}
``````

Map ContainsValue (NOT RECOMMENDED)

This solution is O(N*N), because of the containsValue() method! Every search of containsValue() is O(N).

``````public class Solution {
public boolean isIsomorphic(String s, String t) {
if(s == null || s.length() <= 1) return true;
HashMap<Character, Character> map = new HashMap<Character, Character>();
for(int i = 0 ; i< s.length(); i++){
char a = s.charAt(i);
char b = t.charAt(i);
if(map.containsKey(a)){
if(map.get(a).equals(b))
continue;
else
return false;
}else{
if(!map.containsValue(b))
map.put(a,b);
else return false;

}
}
return true;

}
}
``````