Trie implementation with wildcard values
I am implementing an algorithm for matching directories. Therefore, I have been given a set of valid paths that can include wildcards (denoted by "X"). Then, when I pass an input, I need to know if that input matches one of the paths in my valid set. I am running into a wildcard issue where the wildcard value that is being passed is actually the same as another valid value. Here's an example:
A set of valid paths:
/guest /guest/X /X/guest /member /member/friends /member/X /member/X/friends
Input example:
/member/garbage/friends /member/friends/friends
They should return true, however only the former does. In the first case, since the "garbage" does not match other other possible paths, but at this point there is an option for a wildcard, it will skip it and move on, then it sees "friends" and it knows it is a match. However, my second case doesn't work because it sees friends and goes down a different path in my trie and not in the template. Since there is a correct path with "friends" in this position, he thinks it will be so. Then it sees "friends" again, but from now on there are no correct paths with "friends" in the trie, so it returns false.
My question is, how can I get it to recognize another valid path, even if it is coming off the wrong branch in the trie. Below is the search code and an example of a trie chart.
The search algorithm for my trie looks like this:
private TrieNode searchNode(String input) {
Map<String, TrieNode> children = root.children;
TrieNode t = null;
// break up input into individual tokens
String[] tokenizedLine = input.split("/");
for(int i = 0; i < tokenizedLine.length; i++){
String current = tokenizedLine[i];
if(children.containsKey(current)) {
t = children.get(current);
children = t.children;
}else if(children.containsKey("X")){
t = children.get("X");
children = t.children;
}else{
return null;
}
}
return t;
}
The trie image to be built with my set of sample paths:
When I enter / member / friends / friends my algorithm goes down the highlighted path and stops because no other "friends" are seen after it, but how can I get it to recognize the first "friends" as a wildcard value, so then it will go on and see the second "friends" after the pattern?
Thanks for any help!
source to share
Found it out. I did some backtracking to keep track of the last node where it saw two possible paths. If he finds a dead end in one path, he will return one last time when he sees two possible paths and try the other. The new algorithm looks like this:
private TrieNode searchNode(String input) {
Map<String, TrieNode> children = root.children;
TrieNode t = null;
// Variables for backtrack function
TrieNode alternativeWildcardNode = null;
int wildcardIndex = 0;
Map<String, TrieNode> wildcardChildren = root.children;
// break up input into individual tokens
String[] tokenizedLine = input.split("/");
for(int i = 0; i < tokenizedLine.length; i++){
String current = tokenizedLine[i];
//System.out.println(current);
//System.out.println(Integer.toString(i));
if(children.containsKey(current) && children.containsKey("X")) {
// store current variable state in case we need to back track here
alternativeWildcardNode = children.get("X");
wildcardIndex = i;
wildcardChildren = alternativeWildcardNode.children;
t = children.get(current);
children = t.children;
}else if(children.containsKey(current)) {
t = children.get(current);
children = t.children;
}else if(children.containsKey("X")){
t = children.get("X");
children = t.children;
}else if(alternativeWildcardNode != null){
// if we've reached a branch with no match, but had a possible wildcard previously
// call reset state to the wildcard option instead of static
t = alternativeWildcardNode;
alternativeWildcardNode = null;
i = wildcardIndex;
children = wildcardChildren;
}else{
return null;
}
}
return t;
}
source to share