Google新鲜热乎电面

一种想法是：先找左上角，找到之后对比四个角，如果都相同再逐一比较，虽然还是暴力解，但是实际情况中效率比每次找到左上角就开始比较整个小矩阵会高很多。。

aangel 发表于 2016-9-9 09:18
看到卷积就遁了，
看来这题只能暴力解，估计是面试官想放水吧

啊，我同学在我卷积的基础上想到了一个类似的方法，因为这题是exact match，所以可以任意抽一行和抽一列出来，对于每行每列做KMP，找到那些行列都匹配到的点暴力验证。

在大多数情况下这个做法都非常快，只是对于特别构造的worse case会退化到暴力做法。

啊 lz你pass了嘛

熊笨笨 发表于 2016-10-18 15:33
啊 lz你pass了嘛

并没有 :(

再接再厉 lz加油

补充一下个人对解法的一些看法，这里假设两个矩阵的大小是n^2 和 m^2. ：
1. 卷积确实很快，尤其是matlab里，但是仍然 (m^2 * n^2)，感觉一般用于模糊匹配多. 卷积的优化不了解，不做评论，不过感觉worst cast不会改变，和暴力解区别不是很大，基本都是DFS。楼上有人提到的用求和 或者 histogram 优化接近于BFS后DFS，确实会有显著提高，因为 求和 和 histogram 用类似 sliding window sum 的方法可以做到O(n^2) , 相对于整体的话，这一部分预处理的复杂度基本可以忽略。
2. 我目前能想到的最优解在worst case O(m^2 * n^2)，amortized O(m^2 * n * logn)。不过基本上是纯BFS的算法，类似于histogram的进阶版，思路是参考2D string search, 详见：
http://exceptional-code.blogspot.com/2012/02/solving-boggle-game-recursion-prefix.html

基本思路就是先搜小矩阵的第一个元素，记录下幸存的点然后继续搜小矩阵第二个元素。
大概步骤：
建立hashset1把所有大矩阵的点放进去，建立空hashset2：
外循环遍历小矩阵元素，设为S[i,j], 坐标 i,j =  0 ~ m：
  内循环遍历对每个在hashtable中的位置，设为L[x,y]：
    若 （S[i,j] ＝＝ L[x,y] 并且 hashset1 中 x,y 的上一个点（一般为 x-1,y) 存在）， 则把x,y 放进hashset2中
  内循环结束swap两个hashset
最后输出hashset2是否为空就行了

这个算法的优点是重用性强，对于大量输入,或者小矩阵元素重复率很高的话，使用前缀树(prefix tree or trie)可以大幅提高性能。比如
1 2 1
1 2 2
1 2 3
这种例子就可以逐行建立前缀树搜索，不过面试半个小时我可写不出来前缀树

补充内容 (2016-10-19 15:28):
想想应该是 amortized O(m^2 * n)。如果矩阵中数字取0～K的话，内循环按照 T(n) = T(n/K) + O(n) 来算应该是O(n)

2D Rabin-Karp Linear time Linear space. 呵呵了卷积