18. Trie

 

Trie

It is defined as a Tree based data structure that is used for storing some collection of strings and performing efficient search operations on them.

class Node {

    Node[] alpha;

    boolean endOfWord;

    Node() {

        alpha = new Node[26];

        for (int i = 0; i < 26; i++)

            alpha[i] = null;

        endOfWord = false;

    }

}

class Trie {

    public final static Node root = new Node();

    void insert(String word) {

        Node curr = root;

        for (int i = 0; i < word.length(); i++) {

            int idx = word.charAt(i) - 'a';

            if (curr.alpha[idx] == null)

                curr.alpha[idx] = new Node();

            if (i == word.length() - 1)

                curr.alpha[idx].endOfWord = true;

            curr = curr.alpha[idx];

        }

    }

    boolean search(String word) {

        Node curr = root;

        for (int i = 0; i < word.length(); i++) {

            int idx = word.charAt(i) - 'a';

            if (curr.alpha[idx] == null)

                return false;

            if (i == word.length() - 1 && curr.alpha[idx].endOfWord == false)

                return false;

            curr = curr.alpha[idx];

        }

        return true;

    }

    boolean wordBreak(String key) {

        if (key.length() == 0)

            return true;

        for (int i = 1; i <= key.length(); i++) {

            String firstPart = key.substring(0, i);

            String secondPart = key.substring(i);

            if (search(firstPart) && wordBreak(secondPart))

                return true;

        }

        return false;

    }

    private int countNodes(Node root) {

        int count = 0;

        if (root == null)

            return 0;

        for (int i = 0; i < 26; i++)

            if (root.alpha[i] != null)

                count += countNodes(root.alpha[i]);

        return count + 1;

    }

    int uniqueSubstrings(String key) {

        for (int i = 0; i < key.length(); i++)

            insert(key.substring(i));

        return countNodes(root);

    }

    private static String ans = "";

    String longestWord(Node root, StringBuilder temp) {

        if (root == null)

            return null;

        for (int i = 0; i < 25; i++) {

            if (root.alpha[i] != null && root.alpha[i].endOfWord) {

                temp.append((char) (i + 'a'));

                if (temp.length() > ans.length())

                    ans = temp.toString();

                longestWord(root.alpha[i], temp);

                temp.deleteCharAt(temp.length() - 1);

            }

        }

        return ans;

    }

}