Java solution with comments


  • 0
    W
    class TrieNode {
    	public TrieNode[] children = new TrieNode[26]; // 26个子节点
    	public boolean isWord = false; // 是否是单词
    
    	// Initialize your data structure here.
    	public TrieNode() {
    	}
    }
    
    public class Trie {
    	private TrieNode root; // Trie树中的根节点,TrieNode类型
    
    	public Trie() {
    		root = new TrieNode();
    	}
    
    	// Inserts a word into the trie.
    	public void insert(String word) {
    		TrieNode p = root; // p指向TireTree的根节点
    		for (char c : word.toCharArray()) { // 把每个字符都插入到TireTree中
    			if (p.children[c - 'a'] == null) { // 节点还不存在就new出来
    				p.children[c - 'a'] = new TrieNode();
    			}
                p = p.children[c - 'a']; // 让p指向当前新建出的节点
    		}
    		p.isWord = true; // 标记为单词
    	}
    
    	// Returns if the word is in the trie.
    	public boolean search(String word) {
    		TrieNode p = root; // 指向root,从root开始查找
    		for (char c : word.toCharArray()) { // 对每个字符依次查找
    			if (p.children[c - 'a'] != null) {
    				p = p.children[c - 'a']; // 让p指向当前节点
    			} else {
    				return false; // 字符指向的节点不存在
    			}
    		}
    		return p.isWord; // 是否是单词
    	}
    
    	// Returns if there is any word in the trie
    	// that starts with the given prefix.
    	public boolean startsWith(String prefix) {
    		TrieNode node = root;
    		for (char c : prefix.toCharArray()) {// 对每个字符依次查找
    			if (node.children[c - 'a'] != null) {
    				node = node.children[c - 'a'];
    			} else {
    				return false;
    			}
    		}
    		return true; // startWith
    	}
    }
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie = new Trie();
    // trie.insert("somestring");
    // trie.search("key");

Log in to reply
 

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