y***e
发帖数: 32 | 1 给定一个2D board B，一个dictionary D和一个初始坐标pair p，返回所有
从这个初始坐标开始的词（要求每一词必须在dictionary里）。例如：
B =
[
["APPL"],
["DMCE"],
["AINE"]
]
D = "APPLE", "ADMIN", "BOY"
p = {0, 0}
返回"APPLE", "ADMIN"
非常类似leetcode上的word search。一个额外的问题是如何优化。这个问题主要针对
在对B搜索的时候，从初始坐标开始，可能要遍历所有其他坐标点，非常不efficient。
问如何避免遍历所有其他坐标点。 | h*********3
发帖数: 1 | | m****t
发帖数: 555 | 3 把dictionary建成trie? 这样做词搜索的时候，每搜索到一部分时，都到tire里查。这
样的好处是不用查所有的可能。
有没有更好的办法？ | s********l
发帖数: 998 | 4 这个dictionary是个set吗
要是的话 这道题 bfs就可以了把~ | h*****7
发帖数: 6781 | 5 ......
这描述属于典型的miscommunication | y**********a
发帖数: 824 | 6
......
你这是在吓楼主吧
【在 h*****7 的大作中提到】
: ......
: 这描述属于典型的miscommunication
| f*******w
发帖数: 1243 | 7
我也觉得应该这样做
【在 m****t 的大作中提到】
: 把dictionary建成trie? 这样做词搜索的时候，每搜索到一部分时，都到tire里查。这
: 样的好处是不用查所有的可能。
: 有没有更好的办法？
| m*****k
发帖数: 731 | 8 public static List findWords(char[][] board, List words){
List result = new ArrayList<>();
int[][] deltas = {{0, 1}, {1, 0}};
for(String w: words){
if(w.charAt(0)==board[0][0]){
match(board, 0,0,1, w, deltas, result);
}
}
return result;
}
private static void match(char[][] board, int i, int j, int k, String w,
int[][] deltas, List result) {
if(k==w.length()){
result.add(w);
return;
}
for(int[] indiceDelta: deltas){
int xdelta = indiceDelta[0];
int ydelta = indiceDelta[1];
int x= i + xdelta;
int y =j + ydelta;
if(x>=board.length || y >=board[0].length){
continue;
}
char charXY = board[x][y];
if(charXY == w.charAt(k)){
match(board, x,y,k+1, w, deltas, result);
}
}
} |
|
