Solution: DFS + backtracking Code (Java): import java.io.*; import java.util.*; /* * To execute Java, please define "static void main" on a class * named Solution. * * If you need more classes, simply define them inline. */ class TrieNode { // Initialize your data structure here. TrieNode[] children; boolean leaf; public TrieNode() { children = new TrieNode[26]; } } public class Solution { private TrieNode root; public Solution() { root = new TrieNode(); } // Inserts a word into the trie. public void insert(String word) { if (word == null || word.length() == 0) { return; } TrieNode p = root; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if (p.children[c - 'a'] != null) { p = p.children[c - 'a']; } else { p.children[c - 'a'] = new TrieNode(); p = p.children[c - 'a']; } } p.leaf = true; } // Returns if the word is in the trie. public boolean search(String word) { if (word == null || word.length() == 0) { return false; } TrieNode p = root; for (int i = 0; i < word.
Read full article from Buttercola: EA: Print a Trie
No comments:
Post a Comment