LeetCode 472. Concatenated Words

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2017/01/24/LeetCode-472-Concatenated-Words/

访问原文「LeetCode 472. 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.

题意解析

找到一个数组中所有的连接词。连接词的定义是，这个词完全由数组中已经存在的单词组成。

解法分析

把所有的单词放入HashSet中，然后每个单词去判断。判断的时候使用递归即可。

解题代码

public List<String> findAllConcatenatedWordsInADict(String[] words) {
      Set<String> allWords = new HashSet<>();
      List<String> result = new ArrayList<>();
      for(String word : words){
      	allWords.add(word);
      }
      
      for(String word : words){
      	if(checkConcatenated(word, 0, allWords, 0)){
      		result.add(word);
      	}
      }
      return result;
  }
  
  private boolean checkConcatenated(String word, int index, Set<String> words, int currentWordNum){
  	if(index >= word.length() && currentWordNum >= 2){
  		return true;
  	}
  	for(int i = index; i < word.length(); i++){
  		if(words.contains(word.substring(index, i + 1))){
  			if(checkConcatenated(word, i + 1, words, currentWordNum + 1)){
  				return true;
  			}
  		}
  	}
  	return false;
  }