s*********3
发帖数: 389 | 1 0 1 2 3
0 A B C D
1 S T A T
2 M H R L
3 C T M C
M x N matrix of letters (the above example is 4x4). L is the path length.
The question is: find a path of “START” (L is then 5) in this matrix.
(1, 0), (1,1), (1,2), (2,2), (3,1)
What's the big-O？
Assumptions:
1. We can move either up or down or left or right at any point in time.
2. One item in the matrix can not be used twice to compose of the pattern
string.
用back tracking写了一个，但是不知是否有更好的。 | l*****a
发帖数: 559 | 2 (2,2), (3,1)
这一条不符合啊
1. We can move either up or down or left or right at any point in time.
觉得简单的dfs就行了吧。 | g***s
发帖数: 3811 | 3 I posted it some months ago and it is a DP problem.
O(m*n*L)
length.
【在 s*********3 的大作中提到】
: 0 1 2 3
: 0 A B C D
: 1 S T A T
: 2 M H R L
: 3 C T M C
: M x N matrix of letters (the above example is 4x4). L is the path length.
: The question is: find a path of “START” (L is then 5) in this matrix.
: (1, 0), (1,1), (1,2), (2,2), (3,1)
: What's the big-O？
: Assumptions:
| s*********3
发帖数: 389 | 4 Do you have a link to your post?
Thanks, grass.
【在 g***s 的大作中提到】
: I posted it some months ago and it is a DP problem.
: O(m*n*L)
:
: length.
| s*****y
发帖数: 897 | 5 co-ask. w
【在 s*********3 的大作中提到】
: Do you have a link to your post?
: Thanks, grass.
| x******g
发帖数: 41 | 6 是这个帖子吧
http://www.mitbbs.com/article_t1/JobHunting/31801199_0_2.html
【在 g***s 的大作中提到】
: I posted it some months ago and it is a DP problem.
: O(m*n*L)
:
: length.
| g***s
发帖数: 3811 | 7 yes【 在 xiaoxing (燕麦) 的大作中提到: 】 | d*******l
发帖数: 338 | 8 我觉得这题也可以直接用BFS。先把所有第一个字符匹配上的位置放进队列，队列元素
能表示位置和当前长度就行。然后每次从队列取出一个元素，把它周围的四个元素有条
件的放进队列，直到扩展到第L层，L是目标字符串的长度。
在大多数情况下，时间和空间复杂度应该能降一点，因为少了许多无效的操作 | s*********3
发帖数: 389 | 9 Thanks, grass.
I have looked at your post and have a question.
In your post, you said:
define
f(x,y,z) x,y means the position in the matrix
z means the right z-length sub string of orig search string.
f(x,y,z) true if from x,y, we can find the right z-length sub string of
orig search string; otherwise false
t(z) means the z-th char from the right.
f(x,y,z) =
f(x - 1, y, z -1) && isValidX(x-1) && mtx[x-1,y] == t(z) ||
f(x + 1, y, z -1) && isValidX(x+1) && mtx[x+1,y] == t(z) ||
f(x , y - 1, z -1) && isValidY(y-1) && mtx[x,y-1] == t(z) ||
f(x , y + 1, z -1) && isValidY(y+1) && mtx[x,y+1] == t(z)
It seems that this only considers one case, i.e., mtx[x,y] != t(z). What if mtx[x,y] == t(z)? For the case, should z -= 1 first and then apply for the above logic?
Also, one item in the matrix can't be used twice. Your previous post allowed this.
Thanks.
【在 g***s 的大作中提到】
: yes【 在 xiaoxing (燕麦) 的大作中提到: 】
| i**********e
发帖数: 1145 | 10 不对，BFS 的效率绝对没有 DFS 的还要高。
你可能少考虑了这个情况：
One item in the matrix can not be used twice to compose of the pattern
string.
请问：
BFS 你怎么处理这个状况？
DFS 只要记录 visited cell，就能轻松解决。
BFS 你加入一个 cell 进队列之前怎么确保此元素没用过？
再加上 BFS 是多个不同的路线同时进行而产生复杂的关系，似乎不可能啊？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 d*******l 的大作中提到】
: 我觉得这题也可以直接用BFS。先把所有第一个字符匹配上的位置放进队列，队列元素
: 能表示位置和当前长度就行。然后每次从队列取出一个元素，把它周围的四个元素有条
: 件的放进队列，直到扩展到第L层，L是目标字符串的长度。
: 在大多数情况下，时间和空间复杂度应该能降一点，因为少了许多无效的操作
| | | g***s
发帖数: 3811 | 11 it should be:
f(x,y,z) = mtx[x,y] == t(z) &&
(
f(x - 1, y, z -1) && isValidX(x-1) ||
f(x + 1, y, z -1) && isValidX(x+1) ||
f(x , y - 1, z -1) && isValidY(y-1)||
f(x , y + 1, z -1) && isValidY(y+1)
)
space is O(m*n)[since z only related with z-1] and time is
O(m*n*length).
yes, i found my question was different since node cannot be visited
twice in lz's post. and mine can only visit 4 neighbors but 8 for lz's.
of
【在 s*********3 的大作中提到】
: Thanks, grass.
: I have looked at your post and have a question.
: In your post, you said:
: define
: f(x,y,z) x,y means the position in the matrix
: z means the right z-length sub string of orig search string.
: f(x,y,z) true if from x,y, we can find the right z-length sub string of
: orig search string; otherwise false
: t(z) means the z-th char from the right.
: f(x,y,z) =
| g**e
发帖数: 6127 | 12 op这题，DFS是直观的想法，把访问过的位置mark一下，还需要O(mn) space
dp的话，是不是把你这个个状态方程改改就行？只要检查8个方向，然后检查mtx[x,y]
有没有被访问过
【在 g***s 的大作中提到】
: it should be:
: f(x,y,z) = mtx[x,y] == t(z) &&
: (
: f(x - 1, y, z -1) && isValidX(x-1) ||
: f(x + 1, y, z -1) && isValidX(x+1) ||
: f(x , y - 1, z -1) && isValidY(y-1)||
: f(x , y + 1, z -1) && isValidY(y+1)
: )
: space is O(m*n)[since z only related with z-1] and time is
: O(m*n*length).
| s*********3
发帖数: 389 | 13 For the question I posted, it can only move 4 directions as well.
I have updated the originally post to not allow movements diagonally.
Thanks.
【在 g***s 的大作中提到】
: it should be:
: f(x,y,z) = mtx[x,y] == t(z) &&
: (
: f(x - 1, y, z -1) && isValidX(x-1) ||
: f(x + 1, y, z -1) && isValidX(x+1) ||
: f(x , y - 1, z -1) && isValidY(y-1)||
: f(x , y + 1, z -1) && isValidY(y+1)
: )
: space is O(m*n)[since z only related with z-1] and time is
: O(m*n*length).
| g***s
发帖数: 3811 | 14 DP cannot be used to solve this question since the visited status is huge.
【在 g**e 的大作中提到】
: op这题，DFS是直观的想法，把访问过的位置mark一下，还需要O(mn) space
: dp的话，是不是把你这个个状态方程改改就行？只要检查8个方向，然后检查mtx[x,y]
: 有没有被访问过
| d*******l
发帖数: 338 | 15 我到确实没注意这个条件，不过也不是不能做啊，多条线路相互影响就一个一个的BFS
，就是先对一个可行的开始点BFS，然后再对下一个，每一次BFS都不会影响别的。这个
其实和DFS的方法没什么本质区别了
但现在看下来，这题DFS大概还是效率最高的方法。相比BFS，空间消耗比较少，栈的深
度最多是L也就是目标串的长度。DP所需要的空间最大，直接的做法是O(MNL)，好像可
以优化到O(MN)，但就会麻烦一些。无效操作也比较多，运行时间大概会久一些。不过
时间的渐进复杂度各个方法都是一样的，最坏都是要O(MNL)的，这个好像很难有本质改
善。
【在 i**********e 的大作中提到】
: 不对，BFS 的效率绝对没有 DFS 的还要高。
: 你可能少考虑了这个情况：
: One item in the matrix can not be used twice to compose of the pattern
: string.
: 请问：
: BFS 你怎么处理这个状况？
: DFS 只要记录 visited cell，就能轻松解决。
: BFS 你加入一个 cell 进队列之前怎么确保此元素没用过？
: 再加上 BFS 是多个不同的路线同时进行而产生复杂的关系，似乎不可能啊？
: 一些常见面试题的答案与总结 -
| g***s
发帖数: 3811 | 16 DP can not be used for this question.
DFS, the worst case could be O(3^(n*m)).
For the question that node can be re-visited, DP should be the solution
that interviewer needed. :-)
BFS
【在 d*******l 的大作中提到】
: 我到确实没注意这个条件，不过也不是不能做啊，多条线路相互影响就一个一个的BFS
: ，就是先对一个可行的开始点BFS，然后再对下一个，每一次BFS都不会影响别的。这个
: 其实和DFS的方法没什么本质区别了
: 但现在看下来，这题DFS大概还是效率最高的方法。相比BFS，空间消耗比较少，栈的深
: 度最多是L也就是目标串的长度。DP所需要的空间最大，直接的做法是O(MNL)，好像可
: 以优化到O(MN)，但就会麻烦一些。无效操作也比较多，运行时间大概会久一些。不过
: 时间的渐进复杂度各个方法都是一样的，最坏都是要O(MNL)的，这个好像很难有本质改
: 善。
| d*******l
发帖数: 338 | 17 嗯，仔细想了想，还是因为有不能重复这条限制，不但dp不能解决，直接搜索也会变得
非常低效，DFS要回溯，BFS不方便标记。原来还是想的简单了。其实对大多数情况，搜
索的效率应该还好，但对于某些非常极端的情况，就是指数级的了。我能想到的最糟糕
情况：
A A A A ... A
A ...
...
A ...
A A A A ... B
矩阵是M X N的，目标串是AAAAAAA...AA，一共M X N个A。不知这题有没有什么可行的
办法。
【在 g***s 的大作中提到】
: DP can not be used for this question.
: DFS, the worst case could be O(3^(n*m)).
: For the question that node can be re-visited, DP should be the solution
: that interviewer needed. :-)
:
: BFS
| g***s
发帖数: 3811 | 18 No best solution for this question.
I was asked similar question by google long time ago, but was told the
node can be re-visited. And maybe lz remembered it wrong?
【在 d*******l 的大作中提到】
: 嗯，仔细想了想，还是因为有不能重复这条限制，不但dp不能解决，直接搜索也会变得
: 非常低效，DFS要回溯，BFS不方便标记。原来还是想的简单了。其实对大多数情况，搜
: 索的效率应该还好，但对于某些非常极端的情况，就是指数级的了。我能想到的最糟糕
: 情况：
: A A A A ... A
: A ...
: ...
: A ...
: A A A A ... B
: 矩阵是M X N的，目标串是AAAAAAA...AA，一共M X N个A。不知这题有没有什么可行的
| s*********3
发帖数: 389 | 19 I didn't specifically ask if a node could be re-visited. Based on the given example and what the interviewer asked, I deducted that no nodes could be re-visited during the interview since at that time, the interviewer asked: what if you need to print out all paths?
It was only 10-15 minutes to come up with a solution, so I guess I didn't
spend time (or no time) to ask lots of clarification questions. Maybe that's not good.
So quite frankly, I am not really sure about that right now.
【在 g***s 的大作中提到】
: No best solution for this question.
: I was asked similar question by google long time ago, but was told the
: node can be re-visited. And maybe lz remembered it wrong?
| s*********3
发帖数: 389 | 20 I am a little bit confused about the logic.
Where do we start searching? I would assume from [0,0,length]. What if mtx[0,0] != t(z) which is pattern[0]? Search will stop.
Please clarify.
【在 g***s 的大作中提到】
: it should be:
: f(x,y,z) = mtx[x,y] == t(z) &&
: (
: f(x - 1, y, z -1) && isValidX(x-1) ||
: f(x + 1, y, z -1) && isValidX(x+1) ||
: f(x , y - 1, z -1) && isValidY(y-1)||
: f(x , y + 1, z -1) && isValidY(y+1)
: )
: space is O(m*n)[since z only related with z-1] and time is
: O(m*n*length).
| | | s*****y
发帖数: 897 | 21 Phone interview or onsite?
given example and what the interviewer asked, I deducted that no nodes could
be re-visited during the interview since at that time, the interviewer
asked: what if you need to print out all paths?
's not good.
【在 s*********3 的大作中提到】
: I didn't specifically ask if a node could be re-visited. Based on the given example and what the interviewer asked, I deducted that no nodes could be re-visited during the interview since at that time, the interviewer asked: what if you need to print out all paths?
: It was only 10-15 minutes to come up with a solution, so I guess I didn't
: spend time (or no time) to ask lots of clarification questions. Maybe that's not good.
: So quite frankly, I am not really sure about that right now.
| s*****y
发帖数: 897 | 22 Phone interview or onsite?
given example and what the interviewer asked, I deducted that no nodes could
be re-visited during the interview since at that time, the interviewer
asked: what if you need to print out all paths?
's not good.
【在 s*********3 的大作中提到】
: I didn't specifically ask if a node could be re-visited. Based on the given example and what the interviewer asked, I deducted that no nodes could be re-visited during the interview since at that time, the interviewer asked: what if you need to print out all paths?
: It was only 10-15 minutes to come up with a solution, so I guess I didn't
: spend time (or no time) to ask lots of clarification questions. Maybe that's not good.
: So quite frankly, I am not really sure about that right now.
| g*****k
发帖数: 623 | 23 不明白你这个一个一个的BFS啥意思，而且你怎么实现？用stack of stacks？
你能给个pseudocode吗?
BFS
【在 d*******l 的大作中提到】
: 我到确实没注意这个条件，不过也不是不能做啊，多条线路相互影响就一个一个的BFS
: ，就是先对一个可行的开始点BFS，然后再对下一个，每一次BFS都不会影响别的。这个
: 其实和DFS的方法没什么本质区别了
: 但现在看下来，这题DFS大概还是效率最高的方法。相比BFS，空间消耗比较少，栈的深
: 度最多是L也就是目标串的长度。DP所需要的空间最大，直接的做法是O(MNL)，好像可
: 以优化到O(MN)，但就会麻烦一些。无效操作也比较多，运行时间大概会久一些。不过
: 时间的渐进复杂度各个方法都是一样的，最坏都是要O(MNL)的，这个好像很难有本质改
: 善。
| g***s
发帖数: 3811 | 24 init:
f(x,y,0) = true; x=1..n y=1..m
After dp, get f(x,y,L) = true, that's the start point.
mtx[0,0] != t(z) which is pattern[0]? Search will stop.
【在 s*********3 的大作中提到】
: I am a little bit confused about the logic.
: Where do we start searching? I would assume from [0,0,length]. What if mtx[0,0] != t(z) which is pattern[0]? Search will stop.
: Please clarify.
| g*****k
发帖数: 623 | 25 Why the worst case could be O(3^(n*m))
In the worst case, four options, up,down,left, right all need to do DFS,
Thus you end up with O(4^L).nd you have m*n choices to start the DFS,
so the total time is O(m*n*3^L). L is the length of the pattern.
【在 g***s 的大作中提到】
: DP can not be used for this question.
: DFS, the worst case could be O(3^(n*m)).
: For the question that node can be re-visited, DP should be the solution
: that interviewer needed. :-)
:
: BFS
| g*****k
发帖数: 623 | 26 or directly set
f(x,y,1) = true iff mtx[x,y]=str[L-1] otherwise false
then compute f(x,y,i), for i from 2 to L
【在 g***s 的大作中提到】
: init:
: f(x,y,0) = true; x=1..n y=1..m
: After dp, get f(x,y,L) = true, that's the start point.
:
: mtx[0,0] != t(z) which is pattern[0]? Search will stop.
| g***s
发帖数: 3811 | 27 the worst case L=O(m*n)
【在 g*****k 的大作中提到】
: Why the worst case could be O(3^(n*m))
: In the worst case, four options, up,down,left, right all need to do DFS,
: Thus you end up with O(4^L).nd you have m*n choices to start the DFS,
: so the total time is O(m*n*3^L). L is the length of the pattern.
| s*********3
发帖数: 389 | 28 Phone interview.
杯具。
could
【在 s*****y 的大作中提到】
: Phone interview or onsite?
:
: given example and what the interviewer asked, I deducted that no nodes could
: be re-visited during the interview since at that time, the interviewer
: asked: what if you need to print out all paths?
: 's not good.
| g**e
发帖数: 6127 | 29 phone screen问这题太bt了吧
【在 s*********3 的大作中提到】
: Phone interview.
: 杯具。
:
: could
| s*********3
发帖数: 389 | 30 个人修行不够，虽然interview前复习了一些算法。:)
【在 g**e 的大作中提到】
: phone screen问这题太bt了吧
| | | s*********3
发帖数: 389 | 31 I wrote some Java code afterwards. It seems not very clean. Please comment.
import java.util.*;
//Assumptions:
//1. We can move either up or down or left or right at any point in time,
but not diagonally.
//2. One item in the matrix can not be used twice to compose of the pattern
string.
//3. If different routes lead to the same indexes of matrix items to compose
of the pattern string, display them.
//4. The maximum number of movable steps is (matrix.length - 1) + (matrix[0]
.length - 1) = matrix.length + matrix[0].length - 2.
public class Paths {
class Point {
int row;
int col;
Point(int r, int c) {
row = r;
col = c;
}
int getRow() {
return row;
}
int getCol() {
return col;
}
public boolean equals(Object obj) {
return (this.row == ((Point)obj).row) && (this.col == ((Point)
obj).col);
}
}
ArrayList> uniquePaths(char[][] matrix, int r, int c,
int m, int n, String pattern, int startIndex,
int depthLeft, ArrayList route, ArrayList result,
ArrayList> paths, boolean found) {
if (depthLeft == 0) {
return paths;
}
Point p = new Point(r, c);
//This uses Point class' equals() method to determine if the route
already includes p.
//If it does, it's not a valid route.
//Another way is to mark a visited Point as visited and if it's
encountered again, return immediately.
if (route.contains(p)) {
return paths;
}
route.add(p);
if (matrix[r][c] == pattern.charAt(startIndex)) {
result.add(p);
if (startIndex == pattern.length()-1) {
ArrayList al = (ArrayList)result.clone();
paths.add(al);
System.out.println("The indexes of matrix items to compose
of the pattern string:");
for (int i = 0; i < pattern.length(); i++) {
System.out.print("(" + result.get(i).getRow() + "," +
result.get(i).getCol() + ")");
if (i < pattern.length() - 1) {
System.out.print(",");
}
}
System.out.println();
//Dedugging purpose
System.out.println("The actual route from the top-left
corner to the index of the last character of the pattern string:");
for (Point Point : route) {
System.out.print("(" + Point.getRow() + "," + Point.
getCol() + ")" + " ");
}
System.out.println();
System.out.println();
route.remove(p);
result.remove(p);
return paths;
}
else {
if (!found && ((r+1) < m)) {
uniquePaths(matrix, r+1, c, m, n, pattern, startIndex+1,
depthLeft-1, route, result, paths, found);
}
if (!found && ((c+1) < n)) {
uniquePaths(matrix, r, c+1, m, n, pattern, startIndex+1,
depthLeft-1, route, result, paths, found);
}
if (!found && ((r-1) >= 0)) {
uniquePaths(matrix, r-1, c, m, n, pattern, startIndex+1,
depthLeft-1, route, result, paths, found);
}
if (!found && ((c-1) >= 0)) {
uniquePaths(matrix, r, c-1, m, n, pattern, startIndex+1,
depthLeft-1, route, result, paths, found);
}
}
}
else {
if (!found && ((r+1) < m)) {
uniquePaths(matrix, r+1, c, m, n, pattern, startIndex,
depthLeft-1, route, result, paths, found);
}
if (!found && ((c+1) < n)) {
uniquePaths(matrix, r, c+1, m, n, pattern, startIndex,
depthLeft-1, route, result, paths, found);
}
if (!found && ((r-1) >= 0)) {
uniquePaths(matrix, r-1, c, m, n, pattern, startIndex,
depthLeft-1, route, result, paths, found);
}
if (!found && ((c-1) >= 0)) {
uniquePaths(matrix, r, c-1, m, n, pattern, startIndex,
depthLeft-1, route, result, paths, found);
}
}
if (!found) {
route.remove(p);
result.remove(p);
}
return paths;
}
ArrayList> uniquePaths(char[][] matrix, String pattern)
{
if ((matrix == null) || (matrix.length == 0) || (matrix[0].length ==
0) || pattern == null || pattern.length() == 0
//pattern length is more than matrix.length + matrix[0].
length - 2 since the maximum number of movable steps
//is (matrix.length - 1) + (matrix[0].length - 1) = matrix.
length + matrix[0].length - 2.
|| (pattern.length() > matrix.length + matrix[0].length - 2)
) {
return null;
}
int depthLeft = matrix.length + matrix[0].length - 1;
ArrayList route = new ArrayList();
ArrayList result = new ArrayList();
ArrayList> paths = new ArrayList>(
);
return uniquePaths(matrix, 0, 0, matrix.length, matrix[0].length,
pattern, 0, depthLeft, route, result, paths, false);
}
public static void main (String [] args) {
Paths paths = new Paths();
System.out.println("Test case 1: ");
char[][] matrix = new char[][] {{'A', 'B', 'C', 'D'}, {'S', 'T', 'A'
, 'T'}, {'M', 'H', 'R', 'L'}, {'C', 'T', 'M', 'C'}};
String pattern = "START";
paths.uniquePaths(matrix, pattern);
System.out.println("Test case 2: ");
matrix = new char[][] {{'A', 'B', 'C', 'D'}, {'S', 'T', 'A', 'T'}, {
'M', 'H', 'R', 'L'}, {'C', 'T', 'M', 'T'}};
paths.uniquePaths(matrix, pattern);
//Examples to test exceptional cases
System.out.println("Test case 3: ");
paths.uniquePaths(null, pattern);
paths.uniquePaths(matrix, null);
paths.uniquePaths(null, "");
pattern = "STARTSTART";
paths.uniquePaths(matrix, pattern);
}
}
【在 s*********3 的大作中提到】
: 个人修行不够，虽然interview前复习了一些算法。:)
| i**********e
发帖数: 1145 | 32 I think you need to do DFS from all possible starting points in the grid, not just the top left point.
My code below for reference (does not return the path but return if the word is in the grid or not, should be easy to modify to return the path) :
#include
#include
using namespace std;
const int MAX_ROWS = 100;
const int MAX_COLS = 100;
bool dfs(char grid[][MAX_COLS], int row, int col, int m, int n,
int charIndex, string target, bool visited[][MAX_COLS]) {
if (row < 0 || row > m-1 || col < 0 || col > n-1) return false;
if (visited[row][col]) return false;
if (charIndex >= target.length()) return false;
if (grid[row][col] != target[charIndex]) return false;
charIndex++;
if (charIndex == target.length())
return true;
visited[row][col] = true;
bool ret = dfs(grid, row, col+1, m, n, charIndex, target, visited) ||
dfs(grid, row, col-1, m, n, charIndex, target, visited) ||
dfs(grid, row+1, col, m, n, charIndex, target, visited) ||
dfs(grid, row-1, col, m, n, charIndex, target, visited);
visited[row][col] = false;
return ret;
}
bool boggleSearch(char grid[][MAX_COLS], int m, int n, string word) {
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
bool visited[MAX_ROWS][MAX_COLS] = { false };
if (dfs(grid, r, c, m, n, 0, word, visited))
return true;
}
}
return false;
}
int main() {
char grid[][MAX_COLS] = {
"abcd",
"stat",
"mhrl",
"ctmc"
};
int m = sizeof(grid)/sizeof(grid[0]);
int n = strlen(grid[0]);
cout << boggleSearch(grid, m, n, "star") << endl;
return 0;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | s*****y
发帖数: 897 | 33 So this solution
the character could be only used once?
not just the top left point.
word is in the grid or not, should be easy to modify to return the path) :
【在 i**********e 的大作中提到】
: I think you need to do DFS from all possible starting points in the grid, not just the top left point.
: My code below for reference (does not return the path but return if the word is in the grid or not, should be easy to modify to return the path) :
: #include
: #include
: using namespace std;
: const int MAX_ROWS = 100;
: const int MAX_COLS = 100;
: bool dfs(char grid[][MAX_COLS], int row, int col, int m, int n,
: int charIndex, string target, bool visited[][MAX_COLS]) {
: if (row < 0 || row > m-1 || col < 0 || col > n-1) return false;
| i**********e
发帖数: 1145 | 34 I think so, LZ mentioned this:
One item in the matrix can not be used twice to compose of the pattern
string.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 s*****y 的大作中提到】
: So this solution
: the character could be only used once?
:
: not just the top left point.
: word is in the grid or not, should be easy to modify to return the path) :
| s*****y
发帖数: 897 | 35 Ye.
So for the item that could be used twice, just need to get rid of the
visited[row][col]?
【在 i**********e 的大作中提到】
: I think so, LZ mentioned this:
: One item in the matrix can not be used twice to compose of the pattern
: string.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| d*******l
发帖数: 338 | 36 应该不太好实现，后来注意到每个item不能重复使用的条件，当时没想清楚。这样的话
除了直接dfs，这题实在想不出什么好的办法了。
【在 g*****k 的大作中提到】
: 不明白你这个一个一个的BFS啥意思，而且你怎么实现？用stack of stacks？
: 你能给个pseudocode吗?
:
: BFS
| s*********3
发帖数: 389 | 37 Thanks a lot, ihasleetcode.
Your code is much cleaner. However, I ran your code and found out that the result was not correct.
If you change the pattern to "START", it will return false. It should return true instead.
not just the top left point.
word is in the grid or not, should be easy to modify to return the path) :
【在 i**********e 的大作中提到】
: I think you need to do DFS from all possible starting points in the grid, not just the top left point.
: My code below for reference (does not return the path but return if the word is in the grid or not, should be easy to modify to return the path) :
: #include
: #include
: using namespace std;
: const int MAX_ROWS = 100;
: const int MAX_COLS = 100;
: bool dfs(char grid[][MAX_COLS], int row, int col, int m, int n,
: int charIndex, string target, bool visited[][MAX_COLS]) {
: if (row < 0 || row > m-1 || col < 0 || col > n-1) return false;
|
|
