How to Implement Wildcard Pattern Matching for Strings in Java

The kdn251/interviews repository provides two canonical Java implementations: a Trie-based solution for single-character wildcards (.) and a Dynamic Programming solution for full regular-expression patterns (. and *).

Wildcard pattern matching is a fundamental algorithmic problem commonly encountered in technical interviews. Whether you need to match dictionary words with placeholder characters or implement regex-style search, the approach you choose depends on the specific wildcard semantics required. The open-source repository kdn251/interviews contains production-ready implementations that demonstrate exactly how to handle these scenarios in Java.

Approach 1: Single-Character Wildcard Matching with a Trie

When your pattern only needs to match "any single character" using the . wildcard, a Trie (prefix tree) offers optimal lookup performance. This approach is ideal for dictionary-based search problems where you store a corpus of words and query them with patterns like .ad or b...

Data Structure and Node Design

The implementation in leetcode/trie/AddAndSearchWordDataStructureDesign.java defines a TrieNode class containing a 26-branch array and a terminal storage field:

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String item = "";
}

The children array maps each lowercase letter to its corresponding child node, while item stores the complete word only at terminal nodes.

Insertion Logic

The addWord method inserts strings character-by-character, instantiating nodes on demand:

public void addWord(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        int index = c - 'a';
        if (node.children[index] == null) {
            node.children[index] = new TrieNode();
        }
        node = node.children[index];
    }
    node.item = word;
}

Time complexity for insertion is O(L) where L is the length of the word.

Search with Wildcards

The search method handles literal characters and the . wildcard through a recursive match helper. When encountering a literal, it follows the corresponding child pointer. When encountering ., it explores all non-null children recursively:

public boolean search(String word) {
    return match(word.toCharArray(), 0, root);
}

private boolean match(char[] chs, int k, TrieNode node) {
    if (k == chs.length) {
        return !node.item.equals("");
    }
    if (chs[k] != '.') {
        return node.children[chs[k] - 'a'] != null 
               && match(chs, k + 1, node.children[chs[k] - 'a']);
    } else {
        for (int i = 0; i < node.children.length; i++) {
            if (node.children[i] != null && match(chs, k + 1, node.children[i])) {
                return true;
            }
        }
    }
    return false;
}

Time complexity degrades to O(N · L) in the worst case when the pattern consists entirely of . wildcards, where N ≤ 26 represents the branching factor.

Practical Usage

AddAndSearchWordDataStructure dict = new AddAndSearchWordDataStructure();
dict.addWord("bad");
dict.addWord("dad");
dict.addWord("mad");

// Exact match
System.out.println(dict.search("bad"));   // true
// Wildcard '.' matches any single character
System.out.println(dict.search(".ad"));   // true
System.out.println(dict.search("b.."));   // true
// No match
System.out.println(dict.search("pad"));   // false

Approach 2: Full Regular Expression Matching with Dynamic Programming

For patterns containing both . (any character) and * (zero or more of the preceding element), a Dynamic Programming (DP) solution is required. The implementation in leetcode/dynamic-programming/RegularExpressionMatching.java solves this using a two-dimensional boolean table.

The DP State Definition

The algorithm uses a table dp[i][j] where i ranges from 0 to s.length() and j ranges from 0 to p.length(). The value dp[i][j] is true if the first i characters of string s match the first j characters of pattern p.

State Transitions

The transition logic handles three cases:

1. Direct character match or . wildcard: If p.charAt(j-1) equals s.charAt(i-1) or equals ., then dp[i][j] = dp[i-1][j-1].

2. * wildcard with zero occurrences: If the preceding character does not match the current string character, * must represent zero occurrences of that character. In this case, dp[i][j] = dp[i][j-2].

3. * wildcard with one or many occurrences: When the preceding character matches (or is .), * can represent:

   • Zero occurrences: dp[i][j-2]
   • One occurrence: dp[i-1][j-2] (effectively consuming one character)
   • Many occurrences: dp[i-1][j] (keeping the * active for further matches)

Implementation Details

The isMatch method implements this logic iteratively:

public boolean isMatch(String s, String p) {
    boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    dp[0][0] = true;
    
    // Initialize patterns like a*, a*b*, etc. that can match empty string
    for (int j = 1; j <= p.length(); j++) {
        if (p.charAt(j - 1) == '*' && j >= 2) {
            dp[0][j] = dp[0][j - 2];
        }
    }
    
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 1; j <= p.length(); j++) {
            if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p.charAt(j - 1) == '*') {
                if (j >= 2) {
                    if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {
                        dp[i][j] = dp[i][j - 2]; // Zero occurrence
                    } else {
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
                        // Zero      || One       || Many
                    }
                }
            }
        }
    }
    return dp[s.length()][p.length()];
}

Regex Matching Examples

RegularExpressionMatching matcher = new RegularExpressionMatching();

System.out.println(matcher.isMatch("aa", "a"));      // false
System.out.println(matcher.isMatch("aa", "a*"));     // true (zero or more 'a')
System.out.println(matcher.isMatch("ab", ".*"));     // true (any char zero or more times)
System.out.println(matcher.isMatch("aab", "c*a*b")); // true (zero 'c', two 'a', one 'b')

Summary

• Trie-based matching in leetcode/trie/AddAndSearchWordDataStructureDesign.java efficiently handles single-character . wildcards using a 26-branch tree structure with O(L) insertion and O(26^L) worst-case search complexity.
• Dynamic Programming in leetcode/dynamic-programming/RegularExpressionMatching.java implements full regex semantics supporting both . and * wildcards using a 2D boolean table to track matching states.
• The recursive match method in the Trie solution explores all branches when encountering ., while the DP solution uses systematic table filling to handle complex * quantifier logic.
• Choose the Trie approach for dictionary storage and prefix queries; choose the DP approach when you need quantifiers and full pattern matching against arbitrary strings.

Frequently Asked Questions

What is the time complexity of Trie-based wildcard matching?

Insertion into the Trie runs in O(L) time where L is the word length. Search with wildcards has a worst-case complexity of O(N · L) or O(26^L) when the pattern consists entirely of . characters, as the algorithm must explore all possible branches at each wildcard position.

How does the * wildcard work in the DP solution?

The * wildcard in RegularExpressionMatching.java acts as a quantifier for the preceding character, allowing it to match zero, one, or many occurrences. The DP transition checks three cases: skipping both the character and * (zero occurrences), matching exactly one character, or keeping the * active to match additional characters (many occurrences).

Can these implementations handle multiple wildcards in one pattern?

Yes. Both implementations support multiple wildcards. The Trie-based solution handles multiple . characters by recursively exploring all branches at each wildcard position. The DP solution naturally processes arbitrary combinations of . and * throughout the pattern string by evaluating each position in the table independently.

Where can I find the complete source code?

The complete implementations are available in the kdn251/interviews repository:

• Trie-based solution: [leetcode/trie/AddAndSearchWordDataStructureDesign.java](https://github.com/kdn251/interviews/blob/master/leetcode/trie/AddAndSearchWordDataStructureDesign.java)
• DP-based regex solution: [leetcode/dynamic-programming/RegularExpressionMatching.java](https://github.com/kdn251/interviews/blob/master/leetcode/dynamic-programming/RegularExpressionMatching.java)

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}