一个字符串，增加一个字符，看字典中是否存在

看到这个题 https://www.1point3acres.com/bbs ... d=467732&extra=
想起来的一道面试题：
题目这样子：

给定一个 words of dictionary： String[] dict， 看一个 word 是不是能通过在任意位置增加一个 char 也能是在 dictionary 内，这样递归下去能组成一个 chain，返回最长的 chain 的长度。

我的思路是：
建立有向图：根据长度分成bucket，从长度为1的桶开始，遍历长度为2的桶中的字符串，是否可以用边连起来。

判断两个字符是否差距为1个字符，可以O(len(string)) 复杂度。

另外一种思路是对于当前string，如abc，增加一个字符可以改成 _abc/a_bc/ab_c/abc_，然后再去下一个桶中搜索。但我没想出来如何快速匹配 _abc 这样的字符串

对于楼主最后的疑惑   我觉得直接从a遍历到z？ constant time没关系

zhangzitong001 发表于 2019-3-1 15:17
对于楼主最后的疑惑   我觉得直接从a遍历到z？ constant time没关系

26*n的复杂度吧？

长度为n，每个都有26种可能

zdzapple 发表于 2019/03/01 15:21:55


26*n的复杂度吧？

长度为n，每个都有26种可能

我的意思是 这个操作 你要访问_abc这种类型的 O(1)和O(26) 是一样的.

zdzapple 发表于 2019/03/01 15:21:55


26*n的复杂度吧？

长度为n，每个都有26种可能

不好意思   前提是你所有单词在一个hashmap里面.  

zhangzitong001 发表于 2019-3-1 15:25
不好意思   前提是你所有单词在一个hashmap里面.

所有单子 或者 某个桶 都在hashSet里，我觉得没啥区别，

就是我们如何快速根据当前的curString，判断len(curString) + 1的字符串存在呢

zdzapple 发表于 2019/03/01 15:56:28


所有单子 或者 某个桶 都在hashSet里，我觉得没啥区别，

就是我们如何快速根据当前的curString，判断len(curString) + 1的字符串存在呢

抽象一下就是 如何快速找 前缀为a并且后缀为b的 所有单词.  一个思路就是用trie存所有单词 正向反向. 然后先找前缀为a的所有单词  挨个判断是否在后缀树里面

补充内容 (2019-3-1 16:26):
发现其实不需要这样.  只需要前缀trie. 找到前缀a后 dfs它的children（这里就是我们插入那个字母）然后向下看是否能走出b

好题。
这个rabin karp好像能够把词对词比较的 N^2 降维成 期望N哦。
假设四个字母
abcd
先O（LEN）从右向左计算hash，保留中间计算结果（数组一）。这样你有四个数
这个hash是 每个字母乘以 (prime ^ index) + 右边的hash。
然后从左向右再走一遍，这次计算也要保留中间结果。（数组二）
同时，每次把数组二里左边的值 x prime + 数组一右边的值。这样就有了删除任意字母后的hash。
也是一样，先找，然后confirm。
纸上画画好像work。请comment

14417335 发表于 2019-3-1 22:01
好题。
这个rabin karp好像能够把词对词比较的 N^2 降维成 期望N哦。
假设四个字母

我刚才想了想，如果用trie的话，把字典的字符串预先插入到trie中：

例如 apple

就分别插入 apple / eappl / leapp / pleap / pplea

这样判断 aple 这个字符串的时候：也得循环n次，aple -> a#ple = plea，匹配上pleap

所以复杂度还是O(len^2)

还是你这个方法好！

搭配着桶 + DFS + memo，应该能work

lz我有个想法，我能不能放进桶的时候，就把字符串全部pattern话呢？比如说一个长度为4的单词，abcd，我不把abcd放进长度为4的桶里，相反我放四个pattern，分别是"*bcd","a*cd","ab*d","abc*"，这样我长度为 3 的单词想拓展的时候，比如 bcd, 想拓展，我就拓展成 "*bcd","b*cd","bc*d","bcd*"，用这些candidate长度为4的桶的set里面找就行了。