LeetCode-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"]

Note:
You may assume that all inputs are consist of lowercase letters a-z.

使用dfs

 1 class Solution {//dfs my
 2     public List<String> findWords(char[][] board, String[] words) {
 3         Set<String> set = new HashSet<>(Arrays.asList(words));//数组可能会重复
 4         List<String> list = new ArrayList<>();
 5         if(null==words||0==words.length){
 6             return list;
 7         }
 8         for(String s:set){
 9             if(exist(board,s)){
10                 list.add(s);
11             }
12         }
13         return list;
14     }
15     private boolean exist(char[][] board, String word) {
16         if(null==board||0==board.length){
17             return false;
18         }
19         int row = board.length;
20         int col = board[0].length;
21         boolean[][] flag = new boolean[row][col];
22         char c = word.charAt(0);
23         for (int i = 0; i < row; i++) {
24                 for (int j = 0; j < col; j++) {
25                     if(board[i][j]==c){
26                         flag[i][j]=true;
27                         if(dfs(board,flag,i+1,j,word,1)||dfs(board,flag,i-1,j,word,1)||dfs(board,flag,i,j+1,word,1)||dfs(board,flag,i,j-1,word,1)){
28                             return true;
29                         }
30                         flag[i][j]=false;
31                     }
32                 }
33             }
34         return false;
35     }
36     private boolean dfs(char[][] board, boolean[][] flag,int x,int y,String word,int index){
37         if(index>=word.length()){
38             return true;
39         }
40         if(x<0||y<0||x>=board.length||y>=board[0].length||flag[x][y]){
41             return false;
42         }
43         boolean re = false;
44         if(board[x][y]==word.charAt(index)){
45             flag[x][y]=true;
46             re= dfs(board,flag,x+1,y,word,index+1)||dfs(board,flag,x-1,y,word,index+1)||dfs(board,flag,x,y+1,word,index+1)||dfs(board,flag,x,y-1,word,index+1);
47             flag[x][y]=false;
48         }
49         return re;
50     }
51 
52 }

使用字典树 _mytip

  1 class Solution {
  2     Set<String> set = new HashSet<>();
  3     public List<String> findWords(char[][] board, String[] words) {
  4         if(null==words||0==words.length||null==board||0==board.length){
  5             return new ArrayList<>();
  6         }
  7         Trie trie = new Trie();
  8         for (int i = 0; i < words.length; i++) {
  9             trie.insert(words[i]);
 10         }
 11         TrieNode cur = trie.root;
 12         int row = board.length;
 13         int col = board[0].length;
 14         boolean[][] flag = new boolean[row][col];
 15         char c = words[0].charAt(0);
 16         for (int i = 0; i <row; i++) {
 17             for (int j = 0; j < col; j++) {
 18                 dfs(board,flag,i,j,"",trie);
 19             }
 20         }
 21         return new ArrayList<>(set);
 22     }
 23     private void dfs(char[][] board, boolean[][] flag,int x,int y,String s,Trie trie){
 24         if(x<0||y<0||x>=board.length||y>=board[0].length||flag[x][y]){
 25             return ;
 26         }
 27         s = s+board[x][y];
 28         if(!trie.startsWith(s)){
 29             return;
 30         }
 31         if(trie.search(s)){
 32             set.add(s);
 33         }
 34         flag[x][y]=true;
 35         dfs(board,flag,x+1,y,s,trie);
 36         dfs(board,flag,x-1,y,s,trie);
 37         dfs(board,flag,x,y+1,s,trie);
 38         dfs(board,flag,x,y-1,s,trie);
 39         flag[x][y]=false;
 40     }
 41 
 42 }
 43 
 44 class Trie {//my
 45     TrieNode root ;
 46 
 47     /** Initialize your data structure here. */
 48     public Trie() {
 49         root= new TrieNode();
 50     }
 51 
 52     /** Inserts a word into the trie. */
 53     public void insert(String word) {
 54         TrieNode cur = root;
 55         if(null==cur){
 56             cur = new TrieNode();
 57         }
 58         for (int i = 0; i < word.length(); i++) {
 59             char c = word.charAt(i);
 60             Map<Character,TrieNode> list = cur.children;
 61             if(list.containsKey(c)){
 62                 cur = list.get(c);
 63             }
 64             else{
 65                 TrieNode t = new TrieNode(c);
 66                 cur.children.put(c,t);
 67                 cur = t;
 68             }
 69         }
 70         cur.isWord = true;
 71     }
 72 
 73     /** Returns if the word is in the trie. */
 74     public boolean search(String word) {
 75         TrieNode cur = root;
 76         for (int i = 0; i < word.length(); i++) {
 77             char c = word.charAt(i);
 78             if(null==cur||null==cur.children||0==cur.children.size()){
 79                 return false;
 80             }
 81             Map<Character,TrieNode> list = cur.children;
 82             if(list.containsKey(c)){
 83                 cur = list.get(c);
 84             }
 85             else{
 86                 return false;
 87             }
 88         }
 89         return cur.isWord;
 90     }
 91 
 92     /** Returns if there is any word in the trie that starts with the given prefix. */
 93     public boolean startsWith(String prefix) {
 94         TrieNode cur = root;
 95         for (int i = 0; i < prefix.length(); i++) {
 96             char c = prefix.charAt(i);
 97             if(null==cur||null==cur.children||0==cur.children.size()){
 98                 return false;
 99             }
100             Map<Character,TrieNode> list = cur.children;
101             if(list.containsKey(c)){
102                 cur = list.get(c);
103             }
104             else{
105                 return false;
106             }
107         }
108         return true;
109     }
110 }
111 
112 class TrieNode{
113     Map<Character,TrieNode> children;//使用map存放子节点
114     char val;
115     boolean isWord;
116     TrieNode(){
117         children = new HashMap<>();
118         isWord = false;
119     }
120     TrieNode(char c){
121         children = new HashMap<>();
122         isWord = false;
123         val =c;
124     }
125 }

View Code

使用字典树的优解

 1 class Solution {//mytip
 2     Set<String> set = new HashSet<>();
 3     public List<String> findWords(char[][] board, String[] words) {
 4         if(null==words||0==words.length||null==board||0==board.length){
 5             return new ArrayList<>();
 6         }
 7         Trie trie = new Trie();
 8         for (int i = 0; i < words.length; i++) {
 9             trie.insert(words[i]);
10         }
11         TrieNode cur = trie.root;
12         int row = board.length;
13         int col = board[0].length;
14         boolean[][] flag = new boolean[row][col];
15         char c = words[0].charAt(0);
16         for (int i = 0; i <row; i++) {
17             for (int j = 0; j < col; j++) {
18                 dfs(board,flag,i,j,"",cur);
19             }
20         }
21         return new ArrayList<>(set);
22     }
23     private void dfs(char[][] board, boolean[][] flag,int x,int y,String s,TrieNode cur){
24         if(x<0||y<0||x>=board.length||y>=board[0].length||flag[x][y]){
25             return ;
26         }
27         s = s+board[x][y];
28         if(null==cur.children||0==cur.children.size()||!cur.children.containsKey(board[x][y])){
29             return;
30         }
31         cur = cur.children.get(board[x][y]);
32         if(cur.isWord){
33             set.add(s);
34         }
35     
36         flag[x][y]=true;
37         dfs(board,flag,x+1,y,s,cur);
38         dfs(board,flag,x-1,y,s,cur);
39         dfs(board,flag,x,y+1,s,cur);
40         dfs(board,flag,x,y-1,s,cur);
41         flag[x][y]=false;
42     }
43 
44 }
45 
46 class Trie {//my
47     TrieNode root ;
48 
49     /** Initialize your data structure here. */
50     public Trie() {
51         root= new TrieNode();
52     }
53 
54     /** Inserts a word into the trie. */
55     public void insert(String word) {
56         TrieNode cur = root;
57         if(null==cur){
58             cur = new TrieNode();
59         }
60         for (int i = 0; i < word.length(); i++) {
61             char c = word.charAt(i);
62             Map<Character,TrieNode> list = cur.children;
63             if(list.containsKey(c)){
64                 cur = list.get(c);
65             }
66             else{
67                 TrieNode t = new TrieNode(c);
68                 cur.children.put(c,t);
69                 cur = t;
70             }
71         }
72         cur.isWord = true;
73     }
74 
75 }
76 
77 class TrieNode{
78     Map<Character,TrieNode> children;//使用map存放子节点
79     char val;
80     boolean isWord;
81     TrieNode(){
82         children = new HashMap<>();
83         isWord = false;
84     }
85     TrieNode(char c){
86         children = new HashMap<>();
87         isWord = false;
88         val =c;
89     }
90 }

View Code