2015年10月24日星期六

Leetcode 208 Implement Trie (Prefix Tree)

Implement a trie with insertsearch, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.
Solution 1: Implement problem.
 class TrieNode {  
   // Initialize your data structure here.  
   boolean val=false;  
   TrieNode[] next=new TrieNode[26];  
   public TrieNode() {  
   }  
 }  
 public class Trie {  
   private TrieNode root;  
   public Trie() {  
     root = new TrieNode();  
   }  
   // Inserts a word into the trie.  
   public void insert(String word) {  
     int i=0;  
     TrieNode x=root;  
     while (i<word.length()) {  
       int index=word.charAt(i)-'a';  
       if (x.next[index]==null) x.next[index]=new TrieNode();  
       i++;  
       x=x.next[index];  
     }  
     x.val=true;  
   }  
   // Returns if the word is in the trie.  
   public boolean search(String word) {  
     TrieNode x=root;  
     int i=0;  
     while (i<word.length()) {  
       int index=word.charAt(i)-'a';  
       if (x.next[index]==null) return false;  
       i++;  
       x=x.next[index];  
     }  
     return x.val;  
   }  
   // Returns if there is any word in the trie  
   // that starts with the given prefix.  
   public boolean startsWith(String prefix) {  
     TrieNode x=root;  
     int i=0;  
     while (i<prefix.length()) {  
       int index=prefix.charAt(i)-'a';  
       if (x.next[index]==null) return false;  
       i++;  
       x=x.next[index];  
     }  
     return true;  
   }  
 }  

没有评论:

发表评论