Java simple DFS solution


  • 0
    N

    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++) {
                dict.add(words[i]);
            }
            for(int i=0;i<m;i++) {
                String s=words[i];
                dict.remove(s);
                wordBreak(s, dict, set);
                dict.add(s);
            }
            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)) {
                    set.add(s);
                    return true;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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