老妈要来了，最近有什么好看的肥皂剧吗？# NextGeneration - 我爱宝宝
k*g
1 楼
今天昂赛碰到这题，俺用dfs解的，还借了trie树来帮忙剪枝，大概是这样的：
wordSearch() {
for x
for y
dfs(x, y, res)
return res;
}
dfs(x, y, ..) {
if x,y invalid or not a prefix in trie, return
word += b[x][y]
res visited[x][y] = true
dfs(x-1, y ..)
dfs(x+1, y ..)
dfs(x, y-1 ..)
dfs(x, y+1 ..)
visited[x][y] = false
}
面试官问复杂度，我刚说到wordSearch()里面那个循环里的每一次dfs是O(M*N)，这时
候面试官就说：不对，你在那个dfs里面还有四个dfs，每个都要走O(M*N)的，最后搞下
来，你的这个解法复杂度是O((M*N)!)
我说：那个，图dfs的复杂度应该是O(E+V)，在这里不就是O(M*N)么。于是面试官就给
我在白板上画，说你这个一下哗哗这么走，一下哗哗又那么走啥的，到最后我也搞糊涂
了，到底这个复杂度应该是多少呢？
wordSearch() {
for x
for y
dfs(x, y, res)
return res;
}
dfs(x, y, ..) {
if x,y invalid or not a prefix in trie, return
word += b[x][y]
res visited[x][y] = true
dfs(x-1, y ..)
dfs(x+1, y ..)
dfs(x, y-1 ..)
dfs(x, y+1 ..)
visited[x][y] = false
}
面试官问复杂度，我刚说到wordSearch()里面那个循环里的每一次dfs是O(M*N)，这时
候面试官就说：不对，你在那个dfs里面还有四个dfs，每个都要走O(M*N)的，最后搞下
来，你的这个解法复杂度是O((M*N)!)
我说：那个，图dfs的复杂度应该是O(E+V)，在这里不就是O(M*N)么。于是面试官就给
我在白板上画，说你这个一下哗哗这么走，一下哗哗又那么走啥的，到最后我也搞糊涂
了，到底这个复杂度应该是多少呢？
