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) {
            if(dfs(word, set, "")) list.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.