Easy java solution 229ms


  • 0
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
            Arrays.sort(words, (a, b) -> b.length() - a.length());
            Map<String, Boolean> map = new HashMap<>();
            for (String str: words) map.put(str, true);
            List<String> result = new ArrayList<>();
            for (int i = 0; i < words.length - 1; i++) {
                if (helper(words[i], words[i + 1].length(), map, true)) result.add(words[i]);
            }
            return result;
        }
        
        private boolean helper(String s, int len, Map<String, Boolean> map, boolean ori) {
            // boolean "ori" here is to make sure that the word does not be matched by it self
            if (!ori && map.containsKey(s)) return map.get(s);
            if (s.length() == 0) return true;
            for (int i = 1; i <= len; i++) {
                String temp = s.substring(0, i);
                if ((map.containsKey(temp) && map.get(temp) == true && (!ori || s.length() != i)) && helper(s.substring(i), s.length() - i, map, false)) {
                    map.put(s, true);
                    return true;
                }
            }
            map.put(s, false);
            return false;
        }
    

Log in to reply
 

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