h**o
发帖数: 548 | 1 Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell,
where "adjacent" cells are those horizontally or vertically neighboring. The
same letter cell may not be used more than once.
我知道有人问过了。没答案。
我觉得time 复杂度是m*n*4^(k-1). 也就是m*n*4^k.
m X n is board size, k is word size.
space 复杂度 是： 4^k (recursive)+ m*n (to mark visited board cell)
是这样吗？ |
a*****u
发帖数: 1712 | 2 时间复杂度我跟你想的一样。
空间复杂度好像不对，recuision最深是k层，recursive部分空间复杂度应该是O(k)
★ 发自iPhone App: ChineseWeb 7.8
【在 h**o 的大作中提到】
: Given a 2D board and a word, find if the word exists in the grid.
: The word can be constructed from letters of sequentially adjacent cell,
: where "adjacent" cells are those horizontally or vertically neighboring. The
: same letter cell may not be used more than once.
: 我知道有人问过了。没答案。
: 我觉得time 复杂度是m*n*4^(k-1). 也就是m*n*4^k.
: m X n is board size, k is word size.
: space 复杂度 是： 4^k (recursive)+ m*n (to mark visited board cell)
: 是这样吗？
|
h**o
发帖数: 548 | 3 对应该是k + mn
【在 a*****u 的大作中提到】
: 时间复杂度我跟你想的一样。
: 空间复杂度好像不对，recuision最深是k层，recursive部分空间复杂度应该是O(k)
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
h**o
发帖数: 548 | 4 Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell,
where "adjacent" cells are those horizontally or vertically neighboring. The
same letter cell may not be used more than once.
我知道有人问过了。没答案。
我觉得time 复杂度是m*n*4^(k-1). 也就是m*n*4^k.
m X n is board size, k is word size.
space 复杂度 是： 4^k (recursive)+ m*n (to mark visited board cell)
是这样吗？ |
a*****u
发帖数: 1712 | 5 时间复杂度我跟你想的一样。
空间复杂度好像不对，recuision最深是k层，recursive部分空间复杂度应该是O(k)
★ 发自iPhone App: ChineseWeb 7.8
【在 h**o 的大作中提到】
: Given a 2D board and a word, find if the word exists in the grid.
: The word can be constructed from letters of sequentially adjacent cell,
: where "adjacent" cells are those horizontally or vertically neighboring. The
: same letter cell may not be used more than once.
: 我知道有人问过了。没答案。
: 我觉得time 复杂度是m*n*4^(k-1). 也就是m*n*4^k.
: m X n is board size, k is word size.
: space 复杂度 是： 4^k (recursive)+ m*n (to mark visited board cell)
: 是这样吗？
|
h**o
发帖数: 548 | 6 对应该是k + mn
【在 a*****u 的大作中提到】
: 时间复杂度我跟你想的一样。
: 空间复杂度好像不对，recuision最深是k层，recursive部分空间复杂度应该是O(k)
:
: ★ 发自iPhone App: ChineseWeb 7.8
|
l*******t
发帖数: 79 | 7 能不能解释一下那个4^(k-1)是怎么来的 谢谢！ |
