Java solution with Standard DFS a + Standard Trie


  • 0
    M
            private class TrieNode {
    		Map<Character, TrieNode> childs = new HashMap<>();
    		String word;
    		boolean isWord;
    		public TrieNode() {
    			
    		}
    	}
    	private class Trie{
    		TrieNode root = new TrieNode();
    		public Trie(String[] words) {
    			for (String word : words) insert(word);
    		}
    		private void insert(String s) {
    			TrieNode cur = root;
    			for (char c : s.toCharArray()) {
    				if (!cur.childs.containsKey(c)) cur.childs.put(c, new TrieNode());
    				cur = cur.childs.get(c);
    			}
    			cur.word = s;
    			cur.isWord = true;
    		}
    		private List<String> query(String prefix) {
    			TrieNode cur = root;
    			List<String> list = new ArrayList<>();
    			for (char c : prefix.toCharArray()) {
    				if (!cur.childs.containsKey(c)) return list;
    				cur = cur.childs.get(c);
    			}
    			getAllWords(cur, list);
    			return list;
    		}
    		private void getAllWords(TrieNode cur, List<String> list) {
    			if (cur.isWord) {
    				list.add(cur.word);
    				return;
    			}
    			for (TrieNode node : cur.childs.values()) getAllWords(node, list);
    		}
    	}
    	private void dfs(String[] words, List<String> pre, List<List<String>> lists, Trie trie) {
    		if (pre.size() == words[0].length()) {
    			lists.add(new ArrayList<String>(pre));
    			return;
    		}
    		String prefix = "";
    		int size = pre.size();
    		if (size > 0) {
    			for (int i = 0; i < size; ++i) prefix += pre.get(i).charAt(size);
    		}
    		for (String word : trie.query(prefix)) {
    			pre.add(word);
    			dfs(words, pre, lists, trie);
    			pre.remove(pre.size() - 1);
    		}
    	}
    	public List<List<String>> wordSquares(String[] words) {
    		List<List<String>> lists = new ArrayList<>();
    		if (words == null || words.length == 0) return lists;
    		Trie trie = new Trie(words);
    		dfs(words, new ArrayList<String>(), lists, trie);
    		return lists;
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.