The O(n) Club: Wildcard Word Search—Why Brute Force is for Masochists

The O(n) Club: Wildcard Word Search—Why Brute Force is for Masochists

⚡ TL;DR

If your plan is ‘dump words in an ArrayList and hope your CPU forgives you each search,’ maybe try something from this century: use a Trie. Dot (.) means ‘any single letter’—not a cosmic regex explosion. Here’s the slowpoke version (do NOT use for real projects):

// Don't do this unless you enjoy lag
List<String> words = new ArrayList<>();
void addWord(String word) { words.add(word); }
boolean search(String query) {
    for (String w : words)
        if (matches(query, w)) return true;
    return false;
}
boolean matches(String q, String w) {
    if (q.length() != w.length()) return false;
    for (int i = 0; i < q.length(); i++)
        if (q.charAt(i) != '.' && q.charAt(i) != w.charAt(i)) return false;
    return true;
}

🧠 How Devs Usually Mess This Up

Classic rookie move? Slap every word into a list, then linearly check them one by one. Super fun when you only have three words; absolute pain when Product asks you to scale—turns your app into a digital DMV line. Also, people see a dot and get regex-happy: sorry, here the dot is exactly one letter, not a free-for-all wildcard party.

🔍 What’s Actually Going On

A Trie is like a neat little phonebook robot: every letter is a branch, and a word is a path through the forest. Searching with ‘.‘? It’s like the Choose Your Own Adventure of algorithms—at every dot, you branch out and try every possible letter, but only for a single spot. Most paths are dead ends, and that’s a good thing.

🛠️ PseudoCode

• Make a TrieNode class
  Each node has up to 26 children (for all the English letters you’ll ever need); a boolean tells you if the path makes a word.
• Add a word:
  Start at root, walk the word, create nodes as needed, and slap a true at the end.
• Search:
  Use that recursion magic:
  • If char is ‘.’, try all 26 kids. If any path leads to a win, congrats.
  • If char is a normal letter, just walk that one branch.
  • Return true if you hit a completed word at the right depth.

  // Java-style pseudocode
  boolean search(node, idx) {
    if (idx == query.length) return node.isWord;
    char c = query[idx];
    if (c == '.') for (each child) if (search(child, idx+1)) return true;
    else          return child for c != null && search(child, idx+1);
    return false;
  }

💻 The Code

class WordDictionary {
  private static class TrieNode {
    TrieNode[] kids = new TrieNode[26];
    boolean isWord = false;
  }
  private final TrieNode root = new TrieNode();
  
  public void addWord(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
      int i = c - 'a';
      if (node.kids[i] == null) node.kids[i] = new TrieNode();
      node = node.kids[i];
    }
    node.isWord = true;
  }
   public boolean search(String word) {
    return search(word.toCharArray(), 0, root);
  }
   private boolean search(char[] arr, int idx, TrieNode node) {
    if (idx == arr.length) return node.isWord;
    char c = arr[idx];
    if (c == '.') {
      for (TrieNode child : node.kids)
        if (child != null && search(arr, idx+1, child)) return true;
      return false;
    } else {
      TrieNode child = node.kids[c - 'a'];
      return child != null && search(arr, idx+1, child);
    }
  }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• End node confusion? ‘app’ and ‘apple’ don’t autocompile into the same thing. The isWord marker fixes it.
• Dots get expensive: Each dot makes 26 new possible worlds. Not as bad as checking every word, but don’t overdo it.
• Time complexity: Without wildcards, it’s O(w); with wildcards, it’s O(26^d), d = number of dots.
• Memory: More words means bigger Trie, but way less duplication than lists of strings.

🧠 Interviewer Brain-Tattoo

Brute force is for bug bounties and stress dreams. Trie + backtracking is for people who want an offer letter. Choose wisely.