leetcode472-Concatenated-Words

题目要求

Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example:
Input: [“cat”,”cats”,”catsdogcats”,”dog”,”dogcatsdog”,”hippopotamuses”,”rat”,”ratcatdogcat”]

Output: [“catsdogcats”,”dogcatsdog”,”ratcatdogcat”]

Explanation: “catsdogcats” can be concatenated by “cats”, “dog” and “cats”;
“dogcatsdog” can be concatenated by “dog”, “cats” and “dog”;
“ratcatdogcat” can be concatenated by “rat”, “cat”, “dog” and “cat”.
Note:

1. The number of elements of the given array will not exceed 10,000
2. The length sum of elements in the given array will not exceed 600,000.
3. All the input string will only include lower case letters.
4. The returned elements order does not matter.

现有一个无重复的字符串数组，要求找出所有所有拼接字符串，拼接字符串是指位于该数组中可以由数组中至少两个字符串拼接生成的字符串。

思路一：动态规划

已知短的字符串一定无法由长的字符串构成，因此可以将字符串排序，然后逐个判断当前字符串是否为拼接字符串，判断完毕后将该字符串加入字典中，作为下一个判断拼接字符串的可选子字符串。

这里的自底向上动态规划的思想用于判断是否为拼接字符串，即假设想要知道 substring[0,i] 是否可以拼接生成，并且已经知道 substring[0,j] 可以由其它字符串拼接而成，则只需要判断 substring[i,j] 是否可以为字典中的某个字符串即可。

代码如下：

    public List<String> findAllConcatenatedWordsInADict(String[] words) {if (words == null || words.length == 0) {return Collections.EMPTY_LIST;}
        Arrays.sort(words, Comparator.comparing(String::length));
        Set<String> wordSet = new HashSet<>();
        List<String> result = new ArrayList<>();
        for (String word : words) {if (find(wordSet, word)){result.add(word);
            }
        }
        return result;
    }
    
    public boolean find(Set<String> wordSet, String word) {if (wordSet.isEmpty()) {wordSet.add(word);
            return false;
        }
        boolean[] dp = new boolean[word.length()+1];
        dp[0] = true;
        for (int i = 1; i<=word.length() ; i++) {for (int j = 0 ; j<i ; j++) {if (!dp[j]){continue;}
                if (wordSet.contains(word.substring(j, i))) {dp[i] = true;
                    break;
                }
            }
        }
        wordSet.add(word);
        return dp[word.length()];
    }

思路二：深度优先遍历

深度优先遍历的思想本质上和动态规划思想是类似的，这个是网上网友的答案，还做了另一层优化，即在最开始计算出整个数组中最短的字符串长度，并且以该字符串作为自字符串比对的起始长度。

代码如下：

    public List<String> findAllConcatenatedWordsInADict(String[] words) {List<String> res = new LinkedList<>();
        // corner case 
        if(words == null || words.length == 0) return res;
        
        // 1. Create HashSet
        Set<String> set = new HashSet<>();
        int minLen = Integer.MAX_VALUE;
        for(String word : words){if(word.length() > 0){set.add(word);
                minLen = Math.min(minLen, word.length());
            }            
        }
        
        for(String word : words){if(canCompose(word, 0, minLen, set)) res.add(word);
        }
        return res;
    }
    
    public boolean canCompose(String word, int start, int minLen, Set<String> set){for(int i = start + minLen; i <= word.length() - minLen; i++){if(set.contains(word.substring(start, i)) && (set.contains(word.substring(i)) || canCompose(word, i, minLen, set))) return true;
        }
        return false;
    }