Java simple DFS solution

  • 0

    simple dfs solution
    Algorithm please refer to word break II

    Create a "set" to store the intermediate concatenated words for pruning

    public class Solution {
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            int m=words.length;
            List<String> res=new ArrayList<String>();
            Set<String> dict=new HashSet<String>();
            Set<String> set=new HashSet<String>();
            for(int i=0;i<m;i++) {
            for(int i=0;i<m;i++) {
                String s=words[i];
                wordBreak(s, dict, set);
            for(String str:set) {
                if(dict.contains(str)) res.add(str);
            return res;
        private boolean wordBreak(String s, Set<String> dict, Set<String> set) {
            if(set.contains(s)) return true;
            if(dict.contains(s)) return true;
            int n=s.length();
            for(int i=1;i<n;i++) {
                String left=s.substring(0,i);
                String right=s.substring(i);
                if(dict.contains(left)&&wordBreak(right, dict, set)) {
                    return true;
            return false;

Log in to reply

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