Java Backtracking with Optimization


  • 1
    P

    The idea comes from word-break-ii. Basically, the map is used for memorize initial words. I use count to ensure the word is a concatenated one but not initial word. Besides, I use a map cache to optimize the algo since the last test case is pretty time-cousuming. Every time the substring bids map, the cache will firstly be used to check whether remaining substring is a concatenated string(or initial string) or not.

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
            HashMap<String, Integer> map = new HashMap<>();
            HashMap<String, Integer> cache = new HashMap<>();
            List<String> result = new LinkedList<>();
            for(String word: words)
                map.put(word, 1);
            for(String word: words){
                if(checkConcatenated(word, map, cache, 0))
                    result.add(word);
            }
            return result;
        }
        public boolean checkConcatenated(String word, Map map, Map cache, int count) {
            if(word.equals("") && count >= 2) {
                return true;
            }
            for(int i = 1; i <= word.length(); i++) {
                if((int)map.getOrDefault(word.substring(0, i), 0) == 1) {
                    if((int)cache.getOrDefault(word.substring(i), 0) == 1 || checkConcatenated(word.substring(i), map, cache, count + 1)) {
                        if(!word.substring(i).equals(""))
                            cache.put(word.substring(i), 1);
                        return true;
                    }
                }
            }
            return false;
        }
    

  • 0
    Q

    Clever and concise answer


Log in to reply
 

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