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 both s and t have the same length.
思路1（用两个map）
1. scan char a from S and char b from T in the same time
2. use two int array to mimic hash table: mapAB, mapBA
3. if mapAB[a] == 0 , means I didn't mapping it, assign current b to mapAB[a]
otherwise, means I did mapping it, check b == mapAB[a] ?
4. do the same operation for mapBA
5. why checking two maps at the same time? Coz S: egg -> T: aaa return true
then we still check T: aaa -> S: egg
代码
class Solution {
public boolean isIsomorphic(String s, String t) {
if(s.length()!=t.length()) return false;
// uses the arrays to mimic two hash table
int [] mapAB = new int[256];//ASCII characters
int [] mapBA = new int[256];
for(int i = 0; i< s.length();i++){
char a = s.charAt(i);
char b = t.charAt(i);
// mapAB[a]!=0 means I already mapping it
if(mapAB[a]!=0){
if(mapAB[a]!=b) return false;
}
// mapAB[a]==0 means I haven't mapping it
else{
mapAB[a]= b;
}
// why checking two map? coz S:egg T: aaa would return true if only checking mapAB
if(mapBA[b]!=0){
if(mapBA[b]!=a) return false;
}else{
mapBA[b] = a;
}
}
return true;
}
}
思路2（只用一个map）
1. scan either S or T(assuming they have same length)
2. store the idx of current char in both strings.
if previously stored idx are different from current idx, return false
举例：
S: egg T: aaa
m[e] = 1 m[a+256] = 1
m[g] = 2 occurs that previous m[a+256] = 1 return false
代码
class Solution {
public boolean isIsomorphic(String s, String t) {
if(s.length() != t.length()) return false;
int[] m = new int[512];
for (int i = 0; i < s.length(); i++) {
if (m[s.charAt(i)] != m[t.charAt(i)+256]) return false;
m[s.charAt(i)] = m[t.charAt(i)+256] = i+1;
}
return true;
}
}
/* Why not m[s.charAt(i)] = m[t.charAt(i)+256] = i ?
coz 0 is the default value, we should not use it. otherwise we cannot distinguish between
the default maker and the the marker we made.
S: aa T: ab
i= 0： m[a] = 0 m[a+256] = 0
but m[b+256] is defaulted 0
*/
followup1:
如果输入K个string，判断其中至少两个是Isomorphic Strings， 返回boolean
思路
1. 将所有的given string都转成同一种pattern
ex. foo -> abb
ex. gjk -> abc
ex. pkk -> abb
2. 用一个hashmap来存 transfered word 和其出现的频率。
key ： value(frequency)
ex. foo -> abb ： 1
ex. gjk -> abc : 1
ex. pkk -> abb : 1+1 return true
代码
public boolean findIsomorphic(String[] input) {
// key: transWord, value: its corresponding frequency
Map<String, Integer> map = new HashMap<>();
for (String s : input) {
// transfer each String into same pattern
String transWord = transfer(s);
if (!map.containsKey(transWord)) {
map.put(transWord, 1);
}
// such transWord pattern already in String[]
else {
return true;
}
}
return false;
}
/* pattern: every word start with 'a'
when comes a new letter, map it to cur char,
and increase the value of cur cha
*/
private String transfer(String word) {
Map<Character, Character> map = new HashMap<>();
StringBuilder sb = new StringBuilder();
char cur = 'a';
for (char letter : word.toCharArray()) {
if (!map.containsKey(letter)) {
map.put(letter, cur);
cur++;
}
sb.append(map.get(letter));
}
return sb.toString();
}
followup2:
如果输入K个string， 判断其中任意两两是Isomorphic Strings，返回boolean
即给定K个string都能化成同一种等值的pattern