Concise Java without using Trie Tree


  • 1
    A

    The first dimension of t is for the position characters in the words, the second dimension is for 26 different characters.

    import java.util.*;
    public class WordDictionary {
        Set<String> s=new LinkedHashSet<String>();
        List<Set<Integer>[]> t= new ArrayList();
        List<Integer> len = new ArrayList<Integer>();
        public void addWord(String word) {
            for(int i=0; i<word.length(); i++){
                if(i==t.size()){
                    Set<Integer>[] aa=new HashSet[26];
                    for(int j=0; j<26; j++)
                        aa[j]=new HashSet<Integer>();
                    t.add(aa);
                }
                t.get(i)[word.charAt(i)-'a'].add(s.size());
            }
            s.add(word);
            len.add(word.length());
        }
        public boolean search(String word) {
            if(!len.contains(word.length())) return false;
            if(word.indexOf('.')==-1)
                return s.contains(word);
            else{
                Set<Integer> ss=null;
                for(int i=0;i<word.length() && (ss==null || !ss.isEmpty()); i++)
                    if(word.charAt(i)!='.'){
                        if(ss==null) ss=new HashSet<Integer>(t.get(i)[word.charAt(i)-'a']);
                        else ss.retainAll(t.get(i)[word.charAt(i)-'a']);
                    }
                if(ss==null) return true;
                else{
                    for(int i:ss) if(len.get(i)==word.length())
                        return true;
                    return false;
                }
            }
        }
    }

Log in to reply
 

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