Concated Words

LeetCode Q 472 - Concated 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.
E.g. Input: [“cat”,”cats”,”catsdogcats”,”dog”,”dogcatsdog”,”hippopotamuses”,”rat”,”ratcatdogcat”]
Output: [“catsdogcats”,”dogcatsdog”,”ratcatdogcat”]

Solution : Trie + Backtracking

Code:

public List<String> findAllConcatenatedWordsInADict(String[] words) {
	List<String> res = new ArrayList<>();
	if (words == null || words.length == 0) return res;

	// build the trie
	for (String word: words) {
		if (word.length() == 0) continue;
		insert(word);
	}

	// search for concatenated word
	for (String word: words) {
		if (word.length() == 0) continue;
		if (isConcatenated(word, 0, 0)) res.add(word);
	}

	return res;
}

class TrieNode {
	TrieNode[] parent;
	boolean is End;
	public TrieNode() { parent = new TrieNode[26]; }
}

private final TrieNode root = new TrieNode();

private void insert(String word) {
	TrieNode node = root;
	for (char ch: word.toCharArray()) {
		if (node.children[ch - 'a'] == null) 
			node.children[ch - 'a'] = new TrieNode();
		node = 	node.children[ch - 'a'];
	}
	node.isEnd = true;
}

// Use backtracking the check if the current word is a concatenated word
private boolean isConcatenated(String word, int index, int count) {
	// Boundary case
	if (index >= word.length()) return count > 1;
	
	TrieNode node = root;
	for (int i = index; i < word.length(); i++) {
		char ch = word.charAt(i);
		if (node.children[ch - 'a'] == null) // our constraints
			return false;
		node = node.children[ch - 'a'];
		if (node.isEnd) {
			if (isConcatenated(word, i + 1, count + 1)) // explore
				return true;
		}
	}

	return false;
}