Java 156 ms solution, recursion with cache


  • 1
    H

    I suppose the run time should be O(n^2*k), n is the average length of words and k is number of words?

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
            Set<String> dict = new HashSet<>();
            for (String s: words) dict.add(s);
            Map<String, Boolean> canform = new HashMap<>();
            List<String> res = new ArrayList<>();
            for (String s: words) {
                if (check(s, canform, dict)) res.add(s);
            }
            return res;
        }
        private boolean check(String s, Map<String, Boolean> canform, Set<String> dict) {
            if (canform.containsKey(s)) {
                return canform.get(s);
            } else {
                for (int i = 1; i <= s.length(); i++) {
                    String pre = s.substring(0, i);
                    if (dict.contains(pre)) {
                        String post = s.substring(i);
                        if (dict.contains(post) || check(post, canform, dict)) {
                            canform.put(s, true);
                            return true;
                        }
                    }
                }
                canform.put(s, false);
                return false;
    
            }
        }
    

  • 0
    H

    The worst case time complexity is O(n^3 * k), because substring() cost O(n).

    But it is still a very good method to improve from simple DP due to the cache.


Log in to reply
 

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