Tries

PHOTO EMBED

Tue Jan 17 2023 19:32:57 GMT+0000 (Coordinated Universal Time)

Saved by @Beluga #java

public class Tries {
    static class Node {
        Node[] children = new Node[26];
        boolean endOfWord = false;

        Node() {
            for (int i = 0; i < 26; i++) children[i] = null;
        }
    }

    public static Node root = new Node();

    public static void insert(String word) {
        Node curr = root;
        for (int level = 0; level < word.length(); level++) {
            int idx = word.charAt(level) - 'a';
            if (curr.children[idx] == null) {
                curr.children[idx] = new Node();
            }
            curr = curr.children[idx];
        }
        curr.endOfWord = true;
    }

    public static boolean search(String key) {
        Node curr = root;
        for (int i = 0; i < key.length(); i++) {
            int idx = key.charAt(i) - 'a';
            if (curr.children[idx] == null) return false;
            curr = curr.children[idx];
        }
        return curr.endOfWord;
    }

    public static boolean stringBreak(String key) {
        if(key.length()==0) return true;
        for (int i = 1; i <= key.length(); i++) {
            String word1=key.substring(0,i);
            String word2=key.substring(i);
            if(search(word1) && stringBreak(word2)){
                return true;
            }
        }
        return false;
    }


    public static int countSubstrings(String word){
        for(int i=0;i<word.length();i++){
            insert(word.substring(i));
        }
        return countNodes(root);
    }
    public static int countNodes(Node root){
        if(root==null) return 0;
        int count=0;
        for(int i=0;i<26;i++){
            if(root.children[i]!=null){
                count+=countNodes(root.children[i]);
            }
        }
        return count+1;
    }

    public static String longestWord(String[] words){
        String str="";
        for (String word : words) insert(word);

        return str;
    }
    public static boolean isPresent(String word){
        for()
    }



    public static void main(String[] args) {
        String[] words = {"the", "there", "a", "any", "their", "i", "sam", "samsung","like"};
//        for (String word : words) {
//            insert(word);
//        }

    }
}
content_copyCOPY