LeetCode <bt>79&212 Word Search I&II
原创LeetCode <bt>79&212 Word Search I&II
原创
大学里的混子
修改于 2018-11-27 09:41:41
修改于 2018-11-27 09:41:41
文章被收录于专栏：LeetCode
79.Word Search
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.
Example:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.解法：
public boolean exist(char[][] board, String word) {
boolean[][] visited = new boolean[board.length][board[0].length];
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[i].length; j++){
if((word.charAt(0) == board[i][j]) && search(board, word, i, j, 0,visited)){
return true;
}
}
}
return false;
}
private boolean search(char[][]board, String word, int i, int j, int index,boolean[][] visited){
if(index == word.length()){
return true;
}
if(i >= board.length || i < 0 || j >= board[i].length || j < 0 ||
board[i][j] != word.charAt(index) || visited[i][j]){
return false;
}
visited[i][j] = true;
if(search(board, word, i-1, j, index+1,visited) ||
search(board, word, i+1, j, index+1,visited) ||
search(board, word, i, j-1, index+1,visited) ||
search(board, word, i, j+1, index+1,visited)){
return true;
}
visited[i][j] = false;//回溯的体现
return false;
}这是回溯的典型算法。
解法二：
public boolean isValidArea(int x,int y,char[][] grid){
return x>=0&&x<grid.length&&y>=0&&y<grid[0].length;
}
public boolean exist(char[][] board, String word) {
if (board==null||board.length==0||board[0].length==0) return false;
boolean [][] visit = new boolean[board.length][board[0].length];
int [][] step = {
{-1,0},
{0,1},
{1,0},
{0,-1}
};
for (int i = 0;i<board.length;i++){
for (int j = 0;j<board[0].length;j++){
if (existHelper(board,word,i,j,0,visit,step)) return true;
}
}
return false;
}
public boolean existHelper(char[][] board, String word,int x,int y,int index,boolean [][] visit,int [][] step){
if (index == word.length()-1) return word.charAt(index)==board[x][y];
if (board[x][y] == word.charAt(index)){
visit[x][y] = true;
for (int i = 0 ; i < 4; i++){
int xnew = x + step[i][0];
int ynew = y + step[i][1];
if (isValidArea(xnew,ynew,board)&&!visit[xnew][ynew]){
if(existHelper(board,word,xnew,ynew,index+1,visit,step)) return true;
}
}
visit[x][y] = false;
}
return false;
}
212.Word Search II
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must 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 in a word.
Example:
Input:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
Output: ["eat","oath"]题目大意： 给一个2D board和一个单词集，问单词在board中能够找到的有哪些？
解法一：
我们在word search I的基础上，对所有的单词进行一个判断，如果能找到那么这个单词就是我们所需求的。
public boolean exist(char[][] board, String word,boolean[][] visited) {
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[i].length; j++){
if((word.charAt(0) == board[i][j]) && search(board, word, i, j, 0,visited)){
return true;
}
}
}
return false;
}
private boolean search(char[][]board, String word, int i, int j, int index,boolean[][] visited){
if(index == word.length()){
return true;
}
if(i >= board.length || i < 0 || j >= board[i].length || j < 0 || board[i][j] != word.charAt(index) || visited[i][j]){
return false;
}
visited[i][j] = true;
if(search(board, word, i-1, j, index+1,visited) ||
search(board, word, i+1, j, index+1,visited) ||
search(board, word, i, j-1, index+1,visited) ||
search(board, word, i, j+1, index+1,visited)){
return true;
}
visited[i][j] = false;
return false;
}
public List<String> findWords(char[][] board, String[] words) {
boolean[][] visited = new boolean[board.length][board[0].length];
Set<String> set = new HashSet<>();
for (String word:words){
set.add(word);
}
List<String> res = new ArrayList<>();
for (String word:set){
if (exist(board,word,visited)) res.add(word);
visited = new boolean[board.length][board[0].length];
}
return res;
}
解法二：
这是最优解，采用回溯算法加Trie数的方法。有关于Trie树的知识参考《Trie树的基本原理与实现》
public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
TrieNode root = buildTrie(words);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
dfs (board, i, j, root, res);
}
}
return res;
}
public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
char c = board[i][j];
if (c == '#' || p.next[c - 'a'] == null) return;
p = p.next[c - 'a'];
if (p.word != null) { // found one
res.add(p.word);
p.word = null; // de-duplicate
}
board[i][j] = '#';
if (i > 0) dfs(board, i - 1, j ,p, res);
if (j > 0) dfs(board, i, j - 1, p, res);
if (i < board.length - 1) dfs(board, i + 1, j, p, res);
if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);
board[i][j] = c;
}
public TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
TrieNode p = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (p.next[i] == null) p.next[i] = new TrieNode();
p = p.next[i];
}
p.word = w;
}
return root;
}
class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
}Trie数按照单词的字典顺序，极大的改进了单词查询的时间。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
