三刷 06/2022
Version #1 暴力DFS
这里一旦true以后就没有再做backtracking，直接返回
如果是那种需要加答案到result里面的题型就一定要backtracking
Time - the fanout factor could be N(length of the string) and the depth is M(length of the pattern), so a loose approximate estimate would be O(N^M)
Space - O(M + N)
Runtime: 3 ms, faster than 44.50% of Java online submissions for Word Pattern II.
Memory Usage: 42 MB, less than 62.25% of Java online submissions for Word Pattern II.
class Solution {
public boolean wordPatternMatch(String pattern, String s) {
Map<Character, String> map = new HashMap<>();
Set<String> wordSet = new HashSet<>();
return match(pattern, 0, s, 0, map, wordSet);
}
private boolean match(String pattern, int pIndex, String s, int sIndex, Map<Character, String> map, Set<String> wordSet) {
if (pIndex == pattern.length() && sIndex == s.length()) {
return true;
}
if (pIndex >= pattern.length() || sIndex >= s.length()) {
return false;
}
char p = pattern.charAt(pIndex);
if (map.containsKey(p)) {
String word = map.get(p);
if (sIndex + word.length() <= s.length() && word.equals(s.substring(sIndex, sIndex + word.length()))) {
return match(pattern, pIndex + 1, s, sIndex + word.length(), map, wordSet);
}
return false;
}
for (int end = sIndex + 1; end <= s.length(); end++) {
String word = s.substring(sIndex, end);
if (wordSet.contains(word)) {
continue;
}
map.put(p, word);
wordSet.add(word);
if (match(pattern, pIndex + 1, s, end, map, wordSet)) {
return true;
}
map.remove(p);
wordSet.remove(word);
}
return false;
}
}
感觉就是暴力DFS解法
看了答案也没什么可优化的
顶多每次只传一个substring到下一层然后用一个startsWith(map.get(key))
同样的bug在 'ab' v.s. 'aa' 题意说的是bijection 就是one to one mapping
所以必须再用一个set记录mapped如果已经mapped过的String就不能成为另一个key的value， 即 we cannot have to keys pointing to the same string
52.62 %
class Solution {
public boolean wordPatternMatch(String pattern, String str) {
if (pattern == null || str == null) {
return false;
}
// dfs
return dfs(pattern, 0, str, 0, new HashMap<>(), new HashSet<>());
}
private boolean dfs(String pattern, int pIndex,
String str, int sIndex, Map<Character, String> map, Set<String> mapped) {
if (pIndex == pattern.length() && sIndex == str.length()) {
return true;
}
if (pIndex == pattern.length() || sIndex == str.length()) {
return false;
}
char key = pattern.charAt(pIndex);
if (map.containsKey(key)) {
String matchStr = map.get(key);
for (int i = 0; i < matchStr.length(); i++) {
if (sIndex + i >= str.length() || str.charAt(sIndex + i) != matchStr.charAt(i)) {
return false;
}
}
return dfs(pattern, pIndex + 1, str, sIndex + matchStr.length(), map, mapped);
}
// key -> match str.substring(sIndex, j)
for (int j = sIndex + 1; j <= str.length(); j++) {
String matchStr = str.substring(sIndex, j);
if (mapped.contains(matchStr)) {
continue;
}
mapped.add(matchStr);
map.put(key, str.substring(sIndex, j));
if (dfs(pattern, pIndex + 1, str, j, map, mapped)) {
map.remove(key);
mapped.remove(matchStr);
return true;
}
map.remove(key);
mapped.remove(matchStr);
}
return false;
}
}
一刷
比较正常的DFS
46.65 %
有两个bug
一个是在(sIndex + i >= str.length() || pSubString.charAt(i) != str.charAt(sIndex + i)的时候要注意限制sIndex出界
一个是在下面这个例子
pattern - "ab"
string - "aa"
如果只用一个hashset的话，a和b会同时指向'a'，是不被允许的
所以还要加一个hashset保证每一个entry set里面的string都是唯一的
这个代码还有一些可以优化的地方，下次再改进
public class Solution {
//Map<Character, String> key-char in pattern, value-substring in str
public boolean wordPatternMatch(String pattern, String str) {
if (pattern == null || str == null || pattern.length() > str.length()) return false;
Map<Character, String> map = new HashMap<>();
Set<String> visited = new HashSet<>();
return wordPatternMatch(pattern, str, 0, 0, map, visited);
}
//if map.get(key) == null, trying to match pIndex->pLength substring seperately and do recursion call
//Once we see a 'ture' we are OK to return true after 'backtracking'!
//if map.get(key) != null, check if the value can match the substring in str starts at pIndex
//if false return false, other wise return dfs(next layer)
private boolean wordPatternMatch(String pattern, String str, int pIndex, int sIndex, Map<Character, String> map, Set<String> visited) {
if (pIndex == pattern.length() && sIndex == str.length()) return true;
if (pIndex == pattern.length() || sIndex == str.length()) return false;
Character key = pattern.charAt(pIndex);
String pSubString = map.get(key);
boolean res = false;
//1st time seen
if (pSubString == null) {
for (int i = sIndex + 1; i <= str.length(); i++) {
String sub = str.substring(sIndex, i);
if (visited.contains(sub)) continue;
map.put(key, sub);
visited.add(sub);
//System.out.println(sub);
if (wordPatternMatch(pattern, str, pIndex + 1, i, map, visited)) res = true;
map.remove(key);
visited.remove(sub);
if (res) {
return res;
}
}
} else {
for (int i = 0; i < pSubString.length(); i++) {
if (sIndex + i >= str.length() || pSubString.charAt(i) != str.charAt(sIndex + i)) return false;
}
return wordPatternMatch(pattern, str, pIndex + 1, sIndex + pSubString.length(), map, visited);
}
return false;
}
}
No comments:
Post a Comment