Word Patter I & II
练手easy题。对付bijection（双射）之类的题目，就是两个hashmap互相查。
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;
}
}
跟上面的题基本一样，也是bijection题目。所以首先考虑用HashMap做：
class Solution {
public boolean isIsomorphic(String s, String t) {
if (s == null || t == null || s.length() != t.length())
return false;
Map<Character, Character> s2t = new HashMap<>();
Map<Character, Character> t2s = new HashMap<>();
for (int i = 0; i < s.length(); i++){
char s_ch = s.charAt(i), t_ch = t.charAt(i);
if (!s2t.containsKey(s_ch) && !t2s.containsKey(t_ch)){
s2t.put(s_ch, t_ch);
t2s.put(t_ch, s_ch);
}else{
if (!s2t.containsKey(s_ch))
return false;
if (!t2s.containsKey(t_ch))
return false;
if (s2t.get(s_ch) != t_ch)
return false;
}
}
return true;
}
}
另外一种从Discuss里学来的解法：
因为全是ASCII character（其实是个假设，如果真的面试时碰到，大概还得先向面试官clarify一下），所以可以用int[256]来做map。但是map里存的不是这个char在另一个string里对应的char的ascii值，而是这个char在这个string里上一次出现的index + 1。之所以 + 1 是因为这个int[256]里的值默认为0，这样如果某个char对应的值是0，我们就可以确定它从来没出现过。
class Solution {
public boolean isIsomorphic(String s, String t) {
if (s == null || t == null || s.length() != t.length())
return false;
int[] s2p = new int[256], t2p = new int[256]; // store last seen positions of the char
for (int i = 0; i < s.length(); i++){
char s_ch = s.charAt(i), t_ch = t.charAt(i);
if (s2p[s_ch] != t2p[t_ch])
return false;
s2p[s_ch] = t2p[t_ch] = i+1;
}
return true;
}
}
不是很难的hard题。
跟上一题的思想类似，也是用两个HashMap查来查去，保证bijection。这一题里主要麻烦的地方在于str中的单词不是分割开的，所以要用DFS/Backtracing来分割单词。为了分割单词和keep track of目前考虑的pattern中的char，要用两个指针i 和 j，分别指向pattern中的char和str中substring的开头。
Backtracking的做法如下：
- 如果i和j都到了末尾，就返回true。
- 如果i和j只有一个到了末尾，返回false。因为一边已经map完了另一边还有剩的，不可能建立起来一个bijection。
- 否则的话，如果i指向的char见过，就取出来char之前map到的word，在str中剩下的substr中搜索。如果在开头找到了，就跳过这个char和这个word，接着backtrack；否则return false。
- 否则，在str剩下的部分里遍历所有char可能对应的word。如果word见过，就continue。否则把这对char和word记录在map里，接着backtrack。
class Solution {
public boolean wordPatternMatch(String pattern, String str) {
if (pattern == null || str == null)
return false;
Map<Character, String> pat2str = new HashMap<>();
Map<String, Character> str2pat = new HashMap<>();
return backtrack(pattern, str, 0, 0, pat2str, str2pat);
}
public boolean backtrack(String pattern, String str, int i, int j, Map<Character, String> pat2str, Map<String, Character> str2pat){
int m = pattern.length(), n = str.length();
if (i == m && j == n)
return true;
if (i == m || j == n)
return false;
char ch = pattern.charAt(i);
if (pat2str.containsKey(ch)){
String mapStr = pat2str.get(ch);
if (str.substring(j).indexOf(mapStr) != 0)
return false;
if (backtrack(pattern, str, i+1, j+mapStr.length(), pat2str, str2pat))
return true;
}else{
for (int k = j; k < n; k++){
String substr = str.substring(j, k+1);
if (str2pat.containsKey(substr))
continue;
pat2str.put(ch, substr);
str2pat.put(substr, ch);
if (backtrack(pattern, str, i+1, k+1, pat2str, str2pat))
return true;
pat2str.remove(ch);
str2pat.remove(substr);
}
}
return false;
}
}