Tries
Tue Jan 17 2023 19:32:57 GMT+0000 (Coordinated Universal Time)
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); // } } }
Comments