Simple Java 150 ms(75%) - Using HashSet + DFS


  • 0

    Just do brute force method by checking each substring is present in the word list or not. However, keep track of all the substring created so far.

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> list = new ArrayList<String>();
        Set<String> set = new HashSet(Arrays.asList(words));
    
        for(String word : words) {
            set.remove(word);
            if(dfs(word, set, "")) list.add(word);
            set.add(word);
        }
        return list;
    }
    
    
    private boolean dfs(String word, Set<String> set, String previous) {
        if(!previous.equals("")) set.add(previous);
        if(set.contains(word)) return true;
        
        for(int i = 1; i < word.length(); i++) {
            String prefix = word.substring(0,i);
            if(set.contains(prefix) && 
                dfs(word.substring(i,word.length()), set, previous+prefix)) {
                return true;
            }
        }
        return false;
    }

Log in to reply
 

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