123

ad.java

  public class Solution {

    public class Node {
      char ch;
      boolean end;
      HashMap<Character, Node> next = new HashMap<>();
      public Node(char ch) {
        this.ch = ch;
      }
    }

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
      Node root = new Node('0');

      // build trie;
      for (String word : words) {
        insert(root, word);
      }

      // check word in trie.
      List<String> collection = new ArrayList<>();
      for (String word : words) {
        if (isAllConcatenated(root, root, word, 0, 0)) {
          collection.add(word);
        }
      }

      return collection;
    }

    private boolean isAllConcatenated(
        Node root,
        Node node,
        String word,
        int index,
        int endCount) {
      if (index == word.length())
        return endCount >= 1 && node.end;

      char ch = word.charAt(index);
      if (node.next.containsKey(ch)) {
        // go deep
        boolean goDeep = isAllConcatenated(root, node.next.get(ch), word, index + 1, endCount);
        if (goDeep) {
          return true;
        }
      }

      if (node.end && node != root) {
        // reset to root
        return isAllConcatenated(root, root, word, index, endCount + 1);
      }

      return false;
    }

    public void insert(Node node, String word) {
      for (int i = 0 ; i < word.length() ; ++i) {
        char ch = word.charAt(i);

        // inesrt new node
        if (!node.next.containsKey(ch)) {
          node.next.put(ch, new Node(ch));
        }

        node = node.next.get(ch);
      }
      node.end = true;
    }
  }