hyt*_*ucx 5 string algorithm search
我想这是最常见的面试问题之一,但我无法以有效的方式解决它(有效意味着时间复杂度较低,使用合适的数据结构).问题是这样的:如果有一个m x n matrix字符(比如haystack)和给定char的长度为k的字符串(针).编写一个程序来检查大海捞针是否包含针头.请注意,我们只需要从上到下或从左到右搜索干草堆.例如
Haystack
ahydsfd
sdflddl
dfdfd
dfdl
uifddffdhc
Needle:
hdffi
Output:
Yes Found!!
天真的暴力是O(m*n*k).以下是一些优化的想法.
单一搜索
不是同时搜索水平线而是搜索另一个垂直线,而是同时进行.每当您发现针的第一个字母出现时,请查找从该字母开始的水平和垂直匹配.这不会提高复杂性,但在很多情况下,这可能会减少一半的时间,因为你只会看一次糟糕的开始.
稀有字母
而不是寻找针的第一个字母,寻找针中出现的最稀有字母.这将排除很多可能的匹配.要确定哪些字母最稀有,要么扫描整个电路板,要么使用随机采样.
高效的字符串搜索
使用更好的字符串搜索算法,如Knuth-Morris-Pratt.使用算法分别搜索每一行和每列.我敢打赌,这就是采访者所追求的,因为它将复杂性降低到了O(m*n).
利用短行
我注意到并非所有行都具有相同的长度.当你寻找垂直匹配时,你可以在针头"弹出"袋子后立即停止搜索该行,因为沿着该行的所有针头也将从袋子中退出,因此无法匹配.