package miscellaneous; class TrieNode{ private char character; private TrieNode[] series = new TrieNode[26]; private boolean isEnding; public TrieNode(char character, boolean isEnding) { this.character = character; this.isEnding = isEnding; } public char getCharacter() { return character; } public void setCharacter(char character) { this.character = character; } public TrieNode[] getSeries() { return series; } public void setSeries(TrieNode[] series) { this.series = series; } public boolean isEnding() { return isEnding; } public void setEnding(boolean isEnding) { this.isEnding = isEnding; } }
package miscellaneous; public class TrieDictionary { private TrieNode rootNode = new TrieNode('\0', false); public static void main(String[] args) { new TrieDictionary(); } public TrieDictionary() { String[] str = {"hell", "hello", "well"}; for (int i = 0; i < str.length; i++) { storeWordsInDictionary(str[i], rootNode); //System.out.println(); } System.out.println(checkWordExist("all")); System.out.println(); printAllWordsOfDictionary(rootNode.getSeries(), 0, ""); } private void printAllWordsOfDictionary(TrieNode[] arr, int index, String str) { if(arr==null) return; for (int i = 0; i < arr.length; i++) { if(arr[i]!=null){ printAllWordsOfDictionary(arr[i].getSeries(), 0, str+arr[i].getCharacter()); if(arr[i].isEnding()){ System.out.println(str+arr[i].getCharacter()); } } } } private void storeWordsInDictionary(String word, TrieNode startNode){ for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if(startNode.getSeries()[c-97]==null){ startNode.getSeries()[c-97] = new TrieNode(c, (i==word.length()-1)?true:false); startNode = startNode.getSeries()[c-97]; }else{ startNode = startNode.getSeries()[c-97]; if(i==word.length()-1){ startNode.setEnding(true); } } } } private boolean checkWordExist(String word){ for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); if(rootNode.getSeries()[c-97]==null){ return false; }else{ rootNode = rootNode.getSeries()[c-97]; if(i==word.length()-1){ if(rootNode.isEnding()!=true){ return false; } } } } return true; } }
No comments:
Post a Comment