# How to Implement Wildcard Pattern Matching for Strings in Java

> Learn to implement wildcard pattern matching for strings in Java. Explore Trie and Dynamic Programming solutions for single-character and regex patterns from the kdn251/interviews repo.

- Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews)
- Tags: how-to-guide
- Published: 2026-03-04

---

**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`](https://github.com/kdn251/interviews/blob/main/leetcode/trie/AddAndSearchWordDataStructureDesign.java) defines a `TrieNode` class containing a 26-branch array and a terminal storage field:

```java
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:

```java
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:

```java
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

```java
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`](https://github.com/kdn251/interviews/blob/main/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:

```java
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

```java
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`](https://github.com/kdn251/interviews/blob/main/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`](https://github.com/kdn251/interviews/blob/main/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`](https://github.com/kdn251/interviews/blob/main/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/main/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/main/leetcode/dynamic-programming/RegularExpressionMatching.java)](https://github.com/kdn251/interviews/blob/master/leetcode/dynamic-programming/RegularExpressionMatching.java)