472. Concatenated Words

Solution.java

class Solution {
    
    class TrieNode {
        int idx;
        
        TrieNode[] nodes;
        
        public TrieNode() {
            this.nodes = new TrieNode[26];
            this.idx = -1;
        }
        
        public boolean isEndWord() {
            return this.idx > -1;
        }
    }
    
    private TrieNode root;
    
    public void insertWord(String word, int idx) {
        if(word.equals(""))
            return;
        TrieNode cur = root;
        for(int i = 0; i<word.length(); i++) {
            char c = word.charAt(i);
            if(cur.nodes[c - 'a'] == null) {
                cur.nodes[c - 'a'] = new TrieNode();
            }
            cur = cur.nodes[c - 'a'];
        }
        cur.idx = idx;// if set to be non -1 determines the end of word.
    }
    
    private boolean dfs(String word, TrieNode parent, int wIdx, int origIdx, int depth) {
        if(wIdx >= word.length())
            return false;
        
        char c = word.charAt(wIdx);
        TrieNode cur = parent.nodes[c - 'a'];
        if(cur == null)
            return false;
        if(wIdx == word.length() - 1) {
            boolean result = cur.isEndWord() && cur.idx != origIdx;
            return result;
        }
        if(cur.isEndWord()) {
            if(dfs(word, root, wIdx + 1, origIdx, 0)) {
                return true;
            }
        } 
        return dfs(word, cur, wIdx + 1, origIdx, depth + 1);
    }
    
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        root = new TrieNode();
        int idx = 0;
        for(String word: words) {
            insertWord(word, idx);
            idx ++;
        }
        List<String> res = new ArrayList<>();
        idx = 0;
        for(String word: words) {
            if(dfs(word, root, 0, idx, 0)) {
                res.add(word);
            }
            idx++;
        }
        return res;
    }
}