题目

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.

For example, Given egg, add, return true. Given foo, bar, return false. Given paper, title, return true.

Note: You may assume both s and t have the same length.

用HashMap记录映射表

title & paper
t <=> p
i <=> a
l <=> e
e <=> r


代码

public class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character,Character> ts = new HashMap<>(); // key = t, value = s
Map<Character,Character> st = new HashMap<>(); // key = s, value = t
for (int i = 0; i < s.length(); i++) {
Character cs = s.charAt(i);
Character ct = t.charAt(i);
Character csShouldBe = ts.get(ct);
Character ctShouldBe = st.get(cs);
if (csShouldBe == null && ctShouldBe == null) {
ts.put(ct,cs);
st.put(cs,ct);
} else if (csShouldBe == null || ctShouldBe == null || csShouldBe != cs || ctShouldBe != ct) {
return false;
}
}
return true;
}
}


用数组记录映射表

String中的所有char都属于ASCII字符集，对应[0,255]。这样就可以用一个int[256]来记录映射，键值key相当于数组下标。

代码

public class Solution {
public boolean isIsomorphic(String s, String t) {
char[] ts = new char[256];
char[] st = new char[256];
for (int i = 0; i < s.length(); i++) {
char cs = s.charAt(i);
char ct = t.charAt(i);
char csShouldBe = ts[ct];
char ctShouldBe = st[cs];
if (csShouldBe == '\u0000' && ctShouldBe == '\u0000') {
ts[ct] = cs;
st[cs] = ct;
} else if (csShouldBe == '\u0000' || ctShouldBe == '\u0000' || csShouldBe != cs || ctShouldBe != ct) {
return false;
}
}
return true;
}
}