首页 > 代码库 > LintCode-Word Search II
LintCode-Word Search II
Given a matrix of lower alphabets and a dictionary. Find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position.
Example
Given matrix:
doaf
agai
dcanand dictionary:
{"dog", "dad", "dgdg", "can", "again"}return {"dog", "dad", "can", "again"}
Analysis:
DFS. For every word in the list, check every position of board, if the char at some position matches the first char in the word, then start a DFS at this position.
Solution:
1 public class Solution { 2 /** 3 * @param board: A list of lists of character 4 * @param words: A list of string 5 * @return: A list of string 6 */ 7 public ArrayList<String> wordSearchII(char[][] board, ArrayList<String> words) { 8 ArrayList<String> res = new ArrayList<String>(); 9 if (board.length==0) return res;10 int rowNum = board.length;11 if (board[0].length==0) return res;12 int colNum = board[0].length;13 14 for (int i=0;i<words.size();i++){15 String word = words.get(i);16 if (word.length()==0) continue;17 for (int j=0;j<rowNum;j++){18 boolean valid = false;19 for (int k=0;k<colNum;k++)20 if (board[j][k]==word.charAt(0)){21 boolean[][] visited = new boolean[rowNum][colNum];22 for (int p = 0;p<rowNum;p++)23 Arrays.fill(visited[p],false);24 valid = isValidWord(board,visited,word,0,j,k);25 if (valid){26 res.add(word);27 break;28 }29 }30 if (valid) break;31 }32 }33 34 return res;35 }36 37 public boolean isValidWord(char[][] board, boolean[][] visited, String word, int pos, int x, int y){38 if (x<0 || x>=board.length || y<0 || y>=board[0].length) return false; 39 if (word.charAt(pos)!=board[x][y] || visited[x][y]) return false;40 41 if (pos==word.length()-1)42 return true;43 44 45 visited[x][y] = true;46 if (isValidWord(board,visited,word,pos+1,x+1,y) || isValidWord(board,visited,word,pos+1,x-1,y) || isValidWord(board,visited,word,pos+1,x,y+1) || isValidWord(board,visited,word,pos+1,x,y-1))47 return true;48 else {49 visited[x][y]=false;50 return false;51 }52 }53 }
LintCode-Word Search II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。