title: Trie implementation with wildcard values
body: <p>I'm implementing an algorithm to do directory matching. So I'm given a set of valid paths that can include wildcards (denoted by "X"). Then when I pass in an input I need to know if that input matches with one of the paths in my valid set. I'm running into a problem with the wildcards when a wildcard value that is passed in actually matches with another valid value. Here is an example:</p>
  
  <p>Set of valid paths:</p>
  
  <pre><code>/guest
  /guest/X
  /X/guest
  /member
  /member/friends
  /member/X
  /member/X/friends
  </code></pre>
  
  <p>Example input:</p>
  
  <pre><code>/member/garbage/friends    
  /member/friends/friends
  </code></pre>
  
  <p>These should both return true, however only the first one does. In the first case because "garbage" does not match with another other possible paths but there is an option for a wildcard at this point it will skip it and move on, then it sees "friends" and it knows it's a match. However, my second case does not work because it sees friends and goes down a different path in my trie, not the wildcard path. Because there is a valid path with "friends" in this position it thinks it will be that. Then it sees "friends" again but from this point in the trie there are no valid paths with "friends" so it returns false. </p>
  
  <p>My question is, how can I get it to recognize the other valid path even when it goes down the wrong branch in the trie. My search code and example trie diagram is below.</p>
  
  <p>The search algorithm for my trie is as follows:</p>
  
  <pre><code>private TrieNode searchNode(String input) {
      Map&lt;String, TrieNode&gt; children = root.children;
      TrieNode t = null;
  
      // break up input into individual tokens
      String[] tokenizedLine = input.split("/");
      for(int i = 0; i &lt; 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;
  }
  </code></pre>
  
  <p>An image of the trie that would be built with my sample path set:
  <a href="https://i.stack.imgur.com/HU2q9.png" rel="noreferrer"><img src="https://i.stack.imgur.com/HU2q9.png" alt="enter image description here"></a>
  When I input /member/friends/friends my algorithm is going down the highlighted path and stopping because it does not see another "friends" after, but how can I get it to recognize the first "friends" as a wildcard value instead, so then it will continue and see the second "friends" after the wildcard?</p>
  
  <p>Thanks for any help!</p>