找到相差只有一个字符的string

厉害了各位大神们！！！

步惊云 发表于 2019-2-27 12:47
题描述有点毛病, 这"只在一个position不一样. "是什么意思?

我理解是 s[j] = t[j] for every j in [0,  ...

这种算法，和我直接遍历字典，一个一个和target比较，复杂度一样吧。

补充内容 (2019-3-1 13:30):
不一样，搞错了。

感谢楼主分享

各位用hash方法的需要用rolling hash才能满足expected O(1)时间.
以及题目不给用hash.

14417335 发表于 2019-2-27 03:20
如果用rabin karp algorithm，对于任意一个词，做出除去任意一个字母的hash，这个复杂度是O（M）
n个词， ...

对的这个是期望O(mn)时间的算法.
但是这里需要worst case O(mn), hash是expected O(1).

mgccl 发表于 2019-3-4 13:41
对的这个是期望O(mn)时间的算法.
但是这里需要worst case O(mn), hash是expected O(1).

我当时觉得用hash，则找到的情况的复杂度会小于O(MN)，只有在没找到（worst case）才会是O(MN)。看来还是不能达到要求。

给定不能用Hash的要求，则只有Trie进入思路。但是很容易就O(NMM)。

还请指点。

14417335 发表于 2019-3-4 22:17
我当时觉得用hash，则找到的情况的复杂度会小于O(MN)，只有在没找到（worst case）才会是O(MN)。看来还是 ...

两个trie, 一个是给所有的string, 另一个是给reverse of all strings.
这样两个trie就encode了所有prefix, suffix的信息.
花了O(MN)时间.

有了这个数据结构, 做到对于任意i, 可以O(N)时间测试是否存在两个string, 除了第i个字符都一样.

mgccl 发表于 2019-3-5 02:35
两个trie, 一个是给所有的string, 另一个是给reverse of all strings.
这样两个trie就encode了所有pref ...

没明白的地方：

1. 建立正Trie和反Trie本身就要花费O(MN) running time。这样一来就不再是worst case running time了。

2. 举个例子。现在有下面这些词。我猜你可能要在TrieNode里加List of String Ids。但是复杂度对不上。想不出来如何用O(N)来判断在index=2的时候有相同的词：hello 和 heilo？

hello
handy
abcde
heilo

1. 
   
2. 正Trie                                           反Trie
   
3. 
   
4.         h            a                                     o           e          y
   
5.       e    a           b                                 l               d          d
   
6.     l   i     n          c                             l   i               c          n
   
7.   l       l     d          d                         e       e               b          a
   
8. o           o     y          e                     h           h               a          h
   
9. 
   

复制代码

14417335 发表于 2019-3-5 09:09
没明白的地方：

1. 建立正Trie和反Trie本身就要花费O(MN) running time。这样一来就不再是worst case  ...

1. 目标是worst case O(MN)的啊. 建立trie没有问题. trie只建立了一次.

2. 实际上我们需要的信息不是trie本身, 而是trie能给我们的equivalent classes.

我写了个具体实现.

https://chaoxuprime.com/posts/20 ... ance-exactly-1.html