212.单词搜索II

港控/mmm° 2021-06-22 15:38 422阅读 0赞

//给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。  
//  
// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。  
//  
// 示例:  
// 输入:  
//words = \[“oath”,“pea”,“eat”,“rain”\] and board =  
//\[  
// \[‘o’,‘a’,‘a’,‘n’\],  
// \[‘e’,‘t’,‘a’,‘e’\],  
// \[‘i’,‘h’,‘k’,‘r’\],  
// \[‘i’,‘f’,‘l’,‘v’\]  
//\]  
//  
//输出: \[“eat”,“oath”\]  
//  
// 说明:  
//你可以假设所有输入都由小写字母 a-z 组成。  
//  
// 提示:  
// 你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？  
// 如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何  
//实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。  
//  
// Related Topics 字典树 回溯算法  
//思路1：DFS  
//思路2：字典树，先把候选词生成一棵字典树，

import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.Set;
    
    class Solution { 
    	Set<String> res = new HashSet<>();
    
    	public List<String> findWords(char[][] board, String[] words) { 
    		Trie trie = new Trie(); //新建一个字典树
    		for (String word : words) { 
    			trie.insert(word); // 将候选词插入字典树中
    		}
    		int m = board.length;
    		int n = board[0].length; //获取board的宽高
    		boolean[][] visited = new boolean[m][n]; //新建一个二维数组用来标识是否访问过，牺牲空间换时间
    		//对board元素进行枚举
    		for (int i = 0; i < m; i++) { 
    			for (int j = 0; j < n; j++) { 
    				dfs(board, visited, "", i, j, trie);
    			}
    		}
    		return new ArrayList<>(res);
    	}
    
    	//对board进行dfs遍历
    	public void dfs(char[][] board, boolean[][] visited, String str, int x, int y, Trie trie) { 
    		if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) return; //判断数组是否越界
    		if (visited[x][y]) return; //判断是否访问过
    		str += board[x][y];
    		if (!trie.startsWith(str)) return; //如果不是以str开头，就结束。剪枝操作
    		if (trie.search(str)) { 
    			res.add(str);
    		}
    		visited[x][y] = true;
    		dfs(board, visited, str, x - 1, y, trie);
    		dfs(board, visited, str, x + 1, y, trie);
    		dfs(board, visited, str, x, y - 1, trie);
    		dfs(board, visited, str, x, y + 1, trie);
    		visited[x][y] = false;
    	}
    
    	//以下是字典树的定义
    	class Trie { 
    		class TrieNode { 
    			public char val;
    			public boolean isWord;
    			public TrieNode[] children = new TrieNode[26];
    
    			public TrieNode() { }
    
    			public TrieNode(char val) { 
    				this.val = val;
    			}
    		}
    
    		private TrieNode root;
    
    		/** Initialize your data structure here. */
    		public Trie() { 
    			root = new TrieNode();
    			root.val = ' ';
    		}
    
    		/** Inserts a word into the trie. */
    		public void insert(String word) { 
    			TrieNode ws = root;
    			// 将word插入到字典树
    			for (int i = 0; i < word.length(); i++) { 
    				//取出一个字母
    				char c = word.charAt(i);
    				//看是否已存在该字母，不存在新建孩子，并赋值
    				if (ws.children[c - 'a'] == null) { 
    					ws.children[c - 'a'] = new TrieNode(c);
    				}
    				//指向下一个结点
    				ws = ws.children[c - 'a'];
    			}
    			//走到叶子结点，isWord赋值为true
    			ws.isWord = true;
    		}
    
    		/** Returns if the word is in the trie. */
    		public boolean search(String word) { 
    			TrieNode ws = root;
    			for (int i = 0; i < word.length(); i++) { 
    				char c = word.charAt(i);
    				//如果有节点不在，就返回false
    				if (ws.children[c - 'a'] == null) { 
    					return false;
    				}
    				ws = ws.children[c - 'a'];
    			}
    			//最后看最后结点isWord == true
    			return ws.isWord == true;
    		}
    
    		/** Returns if there is any word in the trie that starts with the given prefix. */
    		public boolean startsWith(String prefix) { 
    			TrieNode ws = root;
    			for (int i = 0; i < prefix.length(); i++) { 
    				char c = prefix.charAt(i);
    				//如果有节点不在，就返回false
    				if (ws.children[c - 'a'] == null) { 
    					return false;
    				}
    				ws = ws.children[c - 'a'];
    			}
    			//能走下去就说明true
    			return true;
    		}
    	}
    }