Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.
Examples:
- pattern = "abab", str = "redblueredblue" should return true.
- pattern = "aaaa", str = "asdasdasdasd" should return true.
- pattern = "aabb", str = "xyzabcxzyabc" should return false.
Notes:
You may assume both pattern and str contains only lowercase letters.
一刷
题解：
我们用map来保存pattern中的character代表的string, 然后对接下来的做匹配，如果不满足，就把该匹配从map中删除。
110ms
public class Solution {
public boolean wordPatternMatch(String pattern, String str) {
Map<Character, String> map = new HashMap<>();//pattern a represent the string
Set<String> set = new HashSet<>();
return isMatch(str, 0, pattern, 0, map, set);
}
private boolean isMatch(String str, int i, String pat, int j, Map<Character, String> map,
Set<String> set){
//base case
if(i == str.length() && j == pat.length()) return true;
if(j == str.length() || j == pat.length()) return false;
char c = pat.charAt(j);
if(map.containsKey(c)){
String s = map.get(c);
//check if we can use it to match str[i,..., i+s.length()]
//startWith: begin at i, start with s
if(!str.startsWith(s, i)) return false;
return isMatch(str, i+s.length(), pat, j+1, map, set);
}
// pattern character does not exist in the map
for(int k = i; k<str.length(); k++){
String p = str.substring(i, k+1);
if(set.contains(p)) continue;
//create or update it
map.put(c, p);
set.add(p);
// continue to match the rest
if(isMatch(str, k+1, pat, j+1, map, set)) return true;
map.remove(c);
set.remove(p);
}
return false;
}
}
用map的containsValue的方法来取代set, 按道理从set中寻找应该会更快，因为containsValue需要遍历。然而反而却慢了。
103ms
public class Solution {
public boolean wordPatternMatch(String pattern, String str) {
Map<Character, String> map = new HashMap<>();//pattern a represent the string
return isMatch(str, 0, pattern, 0, map);
}
private boolean isMatch(String str, int i, String pat, int j, Map<Character, String> map){
//base case
if(i == str.length() && j == pat.length()) return true;
if(j == str.length() || j == pat.length()) return false;
char c = pat.charAt(j);
if(map.containsKey(c)){
String s = map.get(c);
//check if we can use it to match str[i,..., i+s.length()]
//startWith: begin at i, start with s
if(!str.startsWith(s, i)) return false;
return isMatch(str, i+s.length(), pat, j+1, map);
}
// pattern character does not exist in the map
for(int k = i; k<str.length(); k++){
String p = str.substring(i, k+1);
if(map.containsValue(p)) continue;
//create or update it
map.put(c, p);
// continue to match the rest
if(isMatch(str, k+1, pat, j+1, map)) return true;
map.remove(c);
}
return false;
}
}
应该还有更快的方法，留给二刷
二刷
首先能直观想到的办法，backtracking
class Solution {
public boolean wordPatternMatch(String pattern, String str) {
Map<Character, String> map = new HashMap<>();
Set<String> set = new HashSet<>();
str = str.trim();
return bt(pattern, 0, str, 0, map, set);
}
private boolean bt(String pattern, int pPos, String str, int pStr, Map<Character, String> map, Set<String> set ){
if(pPos == pattern.length() && pStr == str.length()) return true;
if(pPos == pattern.length()) return false;
if(pStr == str.length()) return false;
if(map.containsKey(pattern.charAt(pPos))){
String match = map.get(pattern.charAt(pPos));
if(!str.substring(pStr).startsWith(match)) return false;
else{
return bt(pattern, pPos+1, str, pStr + match.length(), map, set);
}
}
else{
for(int i=pStr; i<str.length(); i++){
String sub = str.substring(pStr, i+1);
if(set.contains(sub)) continue;
map.put(pattern.charAt(pPos), sub);
set.add(sub);
if(bt(pattern, pPos+1, str, i+1, map, set)) return true;;
map.remove(pattern.charAt(pPos));
set.remove(sub);
}
}
return false;
}
}
