290. Word Pattern
热手题，对于 bijection mapping 就是两个 hashmap 互相查，和 Isomorphic Strings 一样。
public class Solution {
public boolean wordPattern(String pattern, String str) {
HashMap<String, String> pat2word = new HashMap<>();
HashMap<String, String> word2pat = new HashMap<>();
String[] strs = str.split(" ");
if(strs.length != pattern.length()) return false;
for(int i = 0; i < strs.length; i++){
String pat = "" + pattern.charAt(i);
String word = strs[i];
if(!pat2word.containsKey(pat) && !word2pat.containsKey(word)){
pat2word.put(pat, word);
word2pat.put(word, pat);
} else {
if(!pat2word.containsKey(pat)) return false;
if(!word2pat.containsKey(word)) return false;
if(!pat2word.get(pat).equals(word)) return false;
if(!word2pat.get(word).equals(pat)) return false;
}
}
return true;
}
}
改进了一下，照着Isomorphic Strings的思路仿写了一个别的解法。不过当然是不如两个hash表速度快。
public class Solution {
public boolean wordPattern(String pattern, String str) {
String[] st = str.split(" ");
if (st.length != pattern.length()) return false;
String[] hash = new String[128];
Set<String> set = new HashSet<>();
for (int i = 0; i < pattern.length(); ++i) {
char ch = pattern.charAt(i);
String s = st[i];
if (hash[ch] == null && !set.contains(s)) {
hash[ch] = s;
set.add(s);
} else {
if (hash[ch] == null) return false;
if (!hash[ch].equals(s)) return false;
}
}
return true;
}
}
291. Word Pattern II
犯错1：没考虑到当前的 pat / word 都在 map 里而且合法的情况，这时候需要继续向下探。
犯错2: pattern.length() == 0 代表着搜索的结束，但是不是 return true 的充分条件。所以要在 pattern 为 0 的时候正确结束免得越界，同时也要检查 str.length() 是否也等于 0.
public class Solution {
public boolean wordPatternMatch(String pattern, String str) {
return dfs(pattern, str, new HashMap<String, String>(), new HashMap<String, String>());
}
private boolean dfs(String pattern, String str,
HashMap<String, String> pat2word,
HashMap<String, String> word2pat){
if(pattern.length() == 0) return (str.length() == 0);
String pat = "" + pattern.charAt(0);
for(int j = 0; j < str.length(); j++){
String word = str.substring(0, j + 1);
if(!pat2word.containsKey(pat) && !word2pat.containsKey(word)){
pat2word.put(pat, word);
word2pat.put(word, pat);
if(dfs(pattern.substring(1), str.substring(j + 1), pat2word, word2pat)) return true;
pat2word.remove(pat);
word2pat.remove(word);
} else if(pat2word.containsKey(pat) && word2pat.containsKey(word)){
if(pat2word.get(pat).equals(word) && word2pat.get(word).equals(pat)){
if(dfs(pattern.substring(1), str.substring(j + 1), pat2word, word2pat)) return true;
}
}
/*
else {
if(!pat2word.containsKey(pat)) continue;
if(!word2pat.containsKey(word)) continue;
if(!pat2word.get(pat).equals(word)) continue;
if(!word2pat.get(word).equals(pat)) continue;
}
*/
}
return false;
}
}
这种写法在速度上可以进一步改进，比如当看到 char 已经在 map 时，我们就直接把其对应的 word 取出来，不出问题的话就可以继续，否则可以立刻返回 false 进行剪枝和early termination.
然而下面的代码用时上和原来的没什么不同。。可能是 test case 数量太小吧。面试被问到时作为一个 follow up 优化写上去还是不错的。
public class Solution {
public boolean wordPatternMatch(String pattern, String str) {
return dfs(pattern, str, new HashMap<String, String>(), new HashMap<String, String>());
}
private boolean dfs(String pattern, String str,
HashMap<String, String> pat2word,
HashMap<String, String> word2pat){
if(pattern.length() == 0) return (str.length() == 0);
String pat = "" + pattern.charAt(0);
if(pat2word.containsKey(pat)){
String word = pat2word.get(pat);
if(word.length() > str.length()) return false;
else if(word.equals(str.substring(0, word.length()))){
if(dfs(pattern.substring(1), str.substring(word.length()), pat2word, word2pat)) return true;
} else {
return false;
}
}
for(int j = 0; j < str.length(); j++){
String word = str.substring(0, j + 1);
if(!pat2word.containsKey(pat) && !word2pat.containsKey(word)){
pat2word.put(pat, word);
word2pat.put(word, pat);
if(dfs(pattern.substring(1), str.substring(j + 1), pat2word, word2pat)) return true;
pat2word.remove(pat);
word2pat.remove(word);
} else if(pat2word.containsKey(pat) && word2pat.containsKey(word)){
if(pat2word.get(pat).equals(word) && word2pat.get(word).equals(pat)){
if(dfs(pattern.substring(1), str.substring(j + 1), pat2word, word2pat)) return true;
}
}
/*
else {
if(!pat2word.containsKey(pat)) continue;
if(!word2pat.containsKey(word)) continue;
if(!pat2word.get(pat).equals(word)) continue;
if(!word2pat.get(word).equals(pat)) continue;
}
*/
}
return false;
}
}
205. Isomorphic Strings
总是犯一个错误，把第二个string也写成s，明明是t。
public class Solution {
public boolean isIsomorphic(String s, String t) {
int[] maps = new int[128];
int[] mapt = new int[128];
for (int i = 0; i < s.length(); ++i) {
int chs = (int) s.charAt(i);
int cht = (int) t.charAt(i);
if (maps[chs] == 0 && mapt[cht] == 0) {
maps[chs] = cht;
mapt[cht] = 1;
} else if (maps[chs] != cht) return false;
}
return true;
}
}