1
bcxx 2014-03-14 01:07:25 +08:00
三个方向的 KMP 啊……
|
3
c86jeff 2014-03-14 02:16:02 +08:00
BFS吧
|
4
monkeylyf 2014-03-14 02:25:18 +08:00
先用给定的词做一个prefix tree
然后遍历每个点 对每个点做bfs 同时用prefix tree修枝 |
5
ivanlw 2014-03-14 02:51:56 +08:00
昨天大半夜刚做了这道题:
https://gist.github.com/ivanlw/9534435 |
6
ivanlw 2014-03-14 02:54:42 +08:00
@ivanlw 我用DFS,感觉思路比较自然一些,就是遍历和backtracking
不知道楼上说的BFS要怎么追溯判断到word的哪一步呢?在要queue里面压pair吗? |
7
txx 2014-03-14 03:10:33 +08:00
@ivanlw bfs 最常见的地方就是走迷宫...走迷宫需要干的事情就是记住没一个节点是从哪里走过来的,别再走回去。这个一样啊,记录他走过的字符串就是了。
时间复杂度,极端情况下,即匹配串和字典全都是相同的字母例如a的矩阵和一个全都是a最后一个b的字符串,肯定要遍历全图 从矩阵的上的任意一点走遍全图是 20x20。然后要枚举每个点是20x20次,一共是20^4=160000。 远远小于 10^7可以在1s内出结果。 不过总觉得O(N^4)的时间复杂度 还是可以优化的。 |
9
ivanlw 2014-03-14 04:09:48 +08:00
@txx
BFS更典型的场景应该是求无权图的最短路径吧; DFS场景的是遇到whatever we're looking for的时候就可以返回了,也就是这题中的找到字符串就可以返回了,不一定要遍历地搜索完全图;所需要遍历的是尝试matrix中每个cell的值是否是字符串的第一个字符就行了(就是我exist函数的那个双层loop) |
11
txx 2014-03-14 04:47:39 +08:00 via iPhone
@ivanlw bfs 也不用遍历完全啊 我说的是极端情况,你所说的无权图最短路径 不就是走迷宫么。。。迷宫是没有权的啊。当然有权的话 spfa 也是很不错的选择 还是基于bfs的 队列优化的bellman ford。。虽说不如堆优化的dijkstra 但刷题来说效果还是很让人满意的。扯远了
|
12
bcxx 2014-03-14 08:56:36 +08:00
咦,完全没看到数据规模这么小……
|
13
Wins0n 2014-03-14 09:15:55 +08:00
我也会用DFS
|
22
shenjiaqi 2014-03-14 12:56:31 +08:00
使用trie图,原题spoj上http://wenku.baidu.com/view/a4ac7c25aaea998fcc220e72.html有题解,lz给的题暴力就可以乐
|