刷题分享帖之 291

最近多多少少在刷，不知道第几次了。觉得可以把一些经验分享一下。在做的过程中，也希望能够帮助到别人。
291题。
实在是一个太好的backtracking题，非常不常规的backtracking，只能够把自己的想法通过看别人的优秀范例来写一下：

这应该是比较不典型的backtracking了。
没有用boolean来做check是否被遍历过，而是选用了Set。因为我们是做不同的char到string的对应关系，这个不好用boolean来描述，你不能说是，看过了这个char，然后不合适，来下一个，而你去用boolean做String是否被处理过，也不好表示，除非用二维的boolean，但是，这样的话，再加上char本身，就需要一个三维数组，比较麻烦，不如用Set
用Set的时候，不能够单独用，还需要添加上map，因为，我们终归是要记录下来，我们之前所做的char和String的关系。不像传统的backtracking我们可能需要boolean来查看是否遍历过，这里用map+set来表示是否同样的一个mapping关系已经被处理过。
主函数很简单：
public boolean wordPatternMatch(String pattern, String str) {
Map<Character, String> map = new HashMap<>();
Set<String> set = new HashSet<>();
return isMatch(pattern, 0, str, 0, map, set);
}

下面关于判断isMatch的话，如下的一些注意事项：
1. 若任何时刻，pattern和str的index都到了最末尾，说明match， return true
2. 当1没有return的时候，如果有一方的index到达了终点，说明不match，return false
3. 如果当前char在map中存在，查看是否当前str是否以map中char对应的string开始的，如若不是，返回false，如果是，那么recursion下去
4. 常规backtracking部分：
从str的当前index开始到结束
不断把substring取出来。
如果已经在set中存在，跳过
如果不存在，set中做记录，map中同样记录这个对应关系
然后DFS下去。
结束之后，要删除set 和 map中关于那时候的char和String的信息 （此为backtracking）

参考材料：https://leetcode.com/problems/wo ... cktracking-solution

共勉，加油

随便瞟了一眼。感觉只需map就可以了，查看是否有这个key就知道有没有记录过，没必要再用set了吧。

wisdompeak2 发表于 2019-12-26 13:51
随便瞟了一眼。感觉只需map就可以了，查看是否有这个key就知道有没有记录过，没必要再用set了吧。

判断是bidirectional方向
("ab"， "aa"）->false