simple java HashSets solution 117ms


  • 0
    G

    This is my first time upload my answer 'cause it got accepted which i didnt expect. I'm using HashSet to deal with this problem. My question is that, does it take too much space?
    public HashSet<String> hs[];

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        
        List<String> ret = new ArrayList<>();
        
        if(words == null || words.length == 0 || words[0].length() == 0){
            return ret;
        }
        
        //step 1, save all words into hashTable
        hs = new HashSet[26];
        for (int i = 0; i < hs.length; i++) {
            hs[i] = new HashSet<String>();
        }
        for(String s : words){
            char ch = s.charAt(0);
            hs[ch - 'a'].add(s);
        }
        
        for(String s : words){
            
            for(int i = 1; i < s.length(); i++){
                
                char ch = s.charAt(0);
                if(hs[ch - 'a'].contains(s.substring(0, i)) && helper(s.substring(i, s.length()))){
                    ret.add(s);
                    break;
                }
                
            }
            
        }
        
        return ret;
        
    }
    
    
    public boolean helper(String s){
        
        char ch = s.charAt(0);
        if(hs[ch - 'a'].contains(s)){
            return true;
        }
        for(int i = 1; i < s.length(); i++){
                
            if(hs[ch - 'a'].contains(s.substring(0, i)) && helper(s.substring(i, s.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.