raptor.flaps
BAN USERTo solve this problem I would propose creating a dictionary like a trie structure and searching for words within this structure. Here is the solution.
// author raptor flaps
import java.util.ArrayList;
import java.util.List;
public class StringAndDictionary {
private static Node dictionary;
private static class Node {
char aChar = 0;
boolean isWordBoundary;
Node parent;
Node nextSibling;
Node children;
public Node(Node parent) {
this.parent = parent;
}
public void addWord(String word){
if(isRoot()) {
if(children==null) children = new Node(this);
children.addWordInternal(word);
}
}
public void addWordInternal(String word) {
if(word.length()==0) {
return;
}
if(this.aChar==word.charAt(0) || this.aChar==0 ) {
this.aChar = word.charAt(0);
if(word.length()>1) {
if(this.children==null) children = new Node(this);
children.addWordInternal(word.substring(1));
}
else
isWordBoundary = true;
} else {
if(nextSibling==null) nextSibling = new Node(this.parent);
nextSibling.addWordInternal(word);
}
}
public int matchWord(String word) {
if(word.length()==0)
return 0;
int count = 0;
if(isRoot()) {
count = children.matchWordInternal(word) + this.matchWord(word.substring(1));
}
return count;
}
private int matchWordInternal(String word){
if(word.length()== 0) return 0;
int count = 0;
if(aChar == word.charAt(0)) {
count += isWordBoundary?1:0;
count += children !=null?children.matchWordInternal(word.substring(1)):0;
}else {
if(nextSibling!=null) {
count += nextSibling!=null?nextSibling.matchWordInternal(word):0;
}
}
return count;
}
public boolean isRoot(){
return parent==null;
}
}
public static void addWordToDictionary(String word){
if(dictionary==null) {
dictionary = new Node(null);
}
dictionary.addWord(word);
}
public static int findNumberOfWordsInDictionary(String word,String[] dictionaryWords) {
for(String dictionaryWord :dictionaryWords) {
addWordToDictionary(dictionaryWord.toLowerCase());
}
return dictionary.matchWord(word.toLowerCase());
}
public static void main (String ...args) {
System.out.println(" Found : " + StringAndDictionary.findNumberOfWordsInDictionary("app", new String[]{"app", "left","let", "apple", "applet","jin","jinx"}));
System.out.println(" Found : " + StringAndDictionary.findNumberOfWordsInDictionary("jinx", new String[]{"app", "left","let", "apple", "applet","jin","jinx"}));
}
}
Looked at above proposed solutions. Break the problem into subproblems. Employ use of a stack. I beleive you can achieve performance in linear time. Its simple traverse through the right side first, push rightmost into a stack, then push the left tree and so on. Im sure the algo can be improved.
- raptor.flaps March 26, 2016