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

最近遇到的一个好玩的算法题.
给一个有n个长度为m的string的集合S.
用O(mn)时间测试里面是否有两个string, 只在一个position不一样.


因为看过很多人的attempt. 所以加2个条件.
1. 要worst case running time而不是expected running time. 所以hash的expect O(1)是在这里用不起来的.
2. 程序应该能在45分钟内写出.

jaslihao 发表于 2019-3-1 10:32
其實看兩個string只差一個的定義，是只能在同一個index有區分嗎？如果是的話這個方法對於“abc”，“bcd ...

我理解的是在相同的index上的char有区别。“abc”，“bcd”在相同index上不同的char有三个，所以不符合只差一个的定义。

如果用rabin karp algorithm，对于任意一个词，做出除去任意一个字母的hash，这个复杂度是O（M）
n个词，所以复杂度是O（MxN）。
如果hash找到了，还要再确认一遍。
求comment。

这题就是两循环，外循环从字串位置0到m，内循环遍历所以字串，改掉一个位置，然后放到SET里，如果有重复就得解。

用trie，除去children以外，还存储剩余substring
所以每个新的string写入trie的时候就能比较char是否一样，如果遇到不一样，比较sibling的剩余substring

renatax 发表于 2019-2-28 02:20
用trie，除去children以外，还存储剩余substring
所以每个新的string写入trie的时候就能比较char是否一样 ...

比较SUBSTIRNG的话还能满足楼主的MN时间复杂度吗？如果单纯用TRIE结构就已经是MN的复杂度了？

insomnia001 发表于 2019-2-28 03:46
比较SUBSTIRNG的话还能满足楼主的MN时间复杂度吗？如果单纯用TRIE结构就已经是MN的复杂度了？

用hash比较substring复杂度为constant，
而且找到就break and return，所以worst case才是O（NM）

楼主什么专业的啊

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

其實看兩個string只差一個的定義，是只能在同一個index有區分嗎？如果是的話這個方法對於“abc”，“bcd”不頂用。

但其實稍微換一下變成替換成統一的character比如“*”，
"abc" => "*bc","a*c","ab*"
"bcd" => "*cd","b*c","bc*"
也不會錯誤判斷了