for (char ch : word.toCharArray()) { node.children.putIfAbsent(ch, new TrieNode()); node.children.get(ch).words.add(word); node = node.children.get(ch); } }
public List<String> findByPrefix(String prefix){ List<String> result = new ArrayList<>(); TrieNode node = root;
for (char ch : prefix.toCharArray()) { if (!node.children.containsKey(ch)) return result;
node = node.children.get(ch); }
result.addAll(node.words); return result; } }
public List<List<String>> wordSquares(String[] words) { List<List<String>> results = new ArrayList<>(); if (words == null || words.length == 0) return results; List<String> result = new ArrayList<>(); TrieTree trie = new TrieTree(new TrieNode()); int n = words[0].length();
for (String word : words) trie.insert(word);
for (String word : words) { result.add(word); helper(results, result, trie, n); result.remove(result.size() - 1); }
return results; }
privatevoidhelper(List<List<String>> results, List<String> result, TrieTree trie, int n){ if (result.size() == n) { results.add(new ArrayList(result)); return; }
StringBuilder prefix = new StringBuilder(); int idx = result.size(); for (String res : result) prefix.append(res.charAt(idx));
List<String> words = trie.findByPrefix(prefix.toString());
for (String word : words) { result.add(word); helper(results, result, trie, n); result.remove(result.size() - 1); } }
近期评论