This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Trie { | |
private Map<String, Node> roots = new HashMap<>(); | |
public Trie() {} | |
public Trie(List<String> argInitialWords) { | |
for (String word:argInitialWords) { | |
addWord(word); | |
} | |
} | |
public void addWord(String argWord) { | |
addWord(argWord.toCharArray()); | |
} | |
public void addWord(char[] argWord) { | |
Node currentNode = null; | |
if (!roots.containsKey(Character.toString(argWord[0]))) { | |
roots.put(Character.toString(argWord[0]), new Node(argWord[0], "" + argWord[0])); | |
} | |
currentNode = roots.get(Character.toString(argWord[0])); | |
for (int i = 1; i < argWord.length; i++) { | |
if (currentNode.getChild(argWord[i]) == null) { | |
currentNode.addChild(new Node(argWord[i], currentNode.getValue() + argWord[i])); | |
} | |
currentNode = currentNode.getChild(argWord[i]); | |
} | |
currentNode.setIsWord(true); | |
} | |
public boolean containsPrefix(String argPrefix) { | |
return contains(argPrefix.toCharArray(), false); | |
} | |
public boolean containsWord(String argWord) { | |
return contains(argWord.toCharArray(), true); | |
} | |
public Node getWord(String argString) { | |
Node node = getNode(argString.toCharArray()); | |
return node != null && node.isWord() ? node : null; | |
} | |
public Node getPrefix(String argString) { | |
return getNode(argString.toCharArray()); | |
} | |
@Override | |
public String toString() { | |
return roots.toString(); | |
} | |
private boolean contains(char[] argString, boolean argIsWord) { | |
Node node = getNode(argString); | |
return (node != null && node.isWord() && argIsWord) || (!argIsWord && node != null) ? true : false; | |
} | |
private Node getNode(char[] argString) { | |
Node currentNode = roots.get(Character.toString(argString[0])); | |
for (int i = 1; i < argString.length && currentNode != null; i++) { | |
currentNode = currentNode.getChild(argString[i]); | |
if (currentNode == null) { | |
return null; | |
} | |
} | |
return currentNode; | |
} | |
} | |
public class Node { | |
private final Character ch; | |
private final String value; | |
private Map<String, Node> children = new HashMap<>(); | |
private boolean isValidWord; | |
public Node(char argChar, String argValue) { | |
ch = argChar; | |
value = argValue; | |
} | |
public boolean addChild(Node argChild) { | |
if (children.containsKey(Character.toString(argChild.getChar()))) { | |
return false; | |
} | |
children.put(Character.toString(argChild.getChar()), argChild); | |
return true; | |
} | |
public boolean containsChildValue(char c) { | |
return children.containsKey(Character.toString(c)); | |
} | |
public String getValue() { | |
return value.toString(); | |
} | |
public char getChar() { | |
return ch; | |
} | |
public Node getChild(char c) { | |
return children.get(Character.toString(c)); | |
} | |
public boolean isWord() { | |
return isValidWord; | |
} | |
public void setIsWord(boolean argIsWord) { | |
isValidWord = argIsWord; | |
} | |
public String toString() { | |
return value; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment