java Solution 27ms multidimensional array only


  • 0
    A

    public class ValidWordAbbr {

    private Node[][] dic = new Node[26][26];
    
    public ValidWordAbbr(String[] dictionary) {
        for(String s: dictionary) {
            if(s.isEmpty()) continue;
            int row = s.charAt(0) - 'a';
            int col = s.charAt(s.length()-1) - 'a';
            
            if(dic[row][col] == null) dic[row][col] = new Node(s.length(), s);
            else dic[row][col].add(s.length(), s);
        }
    }
    
    public boolean isUnique(String word) {
        if(word.isEmpty()) return true;
        
        int row = word.charAt(0) - 'a';
        int col = word.charAt(word.length()-1) - 'a';
            
        if(dic[row][col] == null) return true;
        else return dic[row][col].isUnique(word.length(), word);
    }
    
    private static class Node {
        
        Node(int length, String w) {
            if(length == 0) {isUnique = true; word=w;}
            else {
                next = new Node[10];
                next[length%10] = new Node(length/10, w);
            }
        }
        
        void add(int length, String w) {
            if(length == 0) {
                if(word != null) {
                    if(!isUnique || word.equals(w)) return;
                    else isUnique = false;
                } else {isUnique = true; word=w;}
            } else if (next == null) {
                next = new Node[10];
                next[length%10] = new Node(length/10, w);
            } else if(next[length%10] != null) next[length%10].add(length/10, w);
            else next[length%10] = new Node(length/10, w);
        }
        
        boolean isUnique(int length, String w) {
             if(length == 0) {
                if(word != null) {
                    if(isUnique && word.equals(w)) return true;
                    else return false;
                } else return true;
            } else if (next == null) {return true;} 
            else if(next[length%10] != null) return next[length%10].isUnique(length/10, w);
            else return true;
        }
        
        Node[] next = null;
        boolean isUnique = false;
        String word = null;
    }
    

    }


Log in to reply
 

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