childNode = new TrieNode[26];
public void add(String word) {
if (word == null || word.length() == 0) {
for (char c : word.toCharArray()) {
if (curNode.childNode[index] == null) {
curNode.childNode[index] = new TrieNode();
curNode.childNode[index].val = c;
curNode = curNode.childNode[index];
public boolean search(String word) {
if (word == null || word.length() == 0) {
for (char c : word.toCharArray()) {
if (curNode.childNode[index] == null) {
curNode = curNode.childNode[index];
public List<String> findAllConcatenatedWordsInADict(String[] words) {
List<String> res = new ArrayList<>();
if (words == null || words.length == 0) {
for (String word : words) {
for (String word : words) {
if (isConcatenatedWord(word, 0, 0, trie)) {
public boolean isConcatenatedWord(String word, int index, int count, Trie trie) {
// If we are at the end of the current word, check if count is equal to or greater than 1
// A concatenated word should consist of at least two words
if (index == word.length() && count >= 2) {
TrieNode curNode = trie.root;
for (int i = index; i < word.length(); i++) {
int pos = word.charAt(i) - 'a';
if (curNode.childNode[pos] == null) {
// if word[0...i] && word[i+1...n] are found in dict, then the current word is concatenated word
if (curNode.childNode[pos].isWord) {
if (isConcatenatedWord(word, i + 1, count + 1, trie)) {
curNode = curNode.childNode[pos];