天天看点

Leetcode: Word Pattern II

因为目标字符串可以任意划分,所以我们不得不尝试所有可能性。这里通过深度优先搜索的回溯法,对于pattern中每个字母,在str中尝试所有的划分方式,如果划分出来的子串可以用这个字母映射,或者可以建立一个新的字母和字符串的映射关系,我们就继续递归判断下一个pattern中的字母,直到pattern的指针和str的指针同时指到最末

技巧在于,

1. 用HashMap + HashSet来保证一一对应

2. 把HashMap和HashSet用作instance variable, 甚至boolean result也可用作instance variable, 这样任何在递归调用函数里所做的改变,都会保留,而不用把HashMap, HashSet, result加入递归argument