30 lines DFS 146ms Java solution


  • 0
    F

    My solution has 4 steps:

    1. get length of shortest words
    2. convert string array to a set
    3. run dfs only on words that has length >= 2*min_length
    4. once current word added to result list, move to next word in words array.
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> res = new ArrayList<>();
            if(words.length < 3) return res;
    
            Set<String> dict = new HashSet<>();
            int minl = Integer.MAX_VALUE;
            for(String w : words) {
                dict.add(w);
                int len = w.length();
                if(len < minl) minl = len;
            }
    
            for(int i = 0; i < words.length; i++) {
                if(words[i].length() < 2*minl) continue;
                helper(words[i], 0, 0, res, dict);
            }
            return res;
        }
        public void helper(String w, int start, int l, List<String> res, Set<String> dict) {
            if(start == w.length() && l >= 2) {
                res.add(w);
                return;
            }
            for(int i = start+1; i <= w.length(); i++) {
                String pre = w.substring(start, i);
    
                if(dict.contains(pre)) {
                    helper(w, i, l+1, res, dict);
                    if(res.size() > 0 && res.get(res.size()-1).equals(w)) break;
                }
            }
        }
    

Log in to reply
 

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