Glob / Path Pattern Matcher (Go)
Topics: backtracking, string matching, recursion
Problem
Implement the wildcard matching used by routing tables and .gitignore-style configs:
func Match(pattern, name string) bool
? matches exactly one character other than /.* matches a (possibly empty) run of characters not containing / — it doesn't cross a
path-segment boundary.** matches a (possibly empty) run of characters including / — it can span any number
of segments. **/foo also matches foo directly (a **/ can stand for zero segments).- Any other byte matches itself, literally.
Match("*.go", "main.go") == true
Match("*.go", "pkg/main.go") == false // '*' doesn't cross '/'
Match("**/main.go", "pkg/main.go") == true
Match("a/**/b", "a/x/y/b") == true
Match("a/**/b", "a/b") == true // '**' can match zero segments
Match("a?c", "a/c") == false // '?' doesn't match '/'
Key concepts
- Why backtracking: a
* doesn't know in advance how much of name it should consume — that
depends on whether the rest of the pattern then matches the rest of the name. So try consuming
0 characters, recurse; if that fails, try 1, then 2, … up to the next / (or, for **, to the end
of name). The first consumption length that lets the rest of the pattern match is the answer; if
none does, this branch fails and the caller (an enclosing *) backtracks to try a different split.
** is the same idea without the / boundary — plus the special case that **/ can also
vanish entirely, so **/build matches a top-level build and not just a nested one.- Termination: each recursive call consumes at least one byte of
pattern (for ? and literal
bytes) or shrinks the search window for */**, so the recursion always terminates — the
exponential cost comes from the branching, not non-termination. TestMatch_RequiresBacktracking
has a pattern where a greedy "consume as much as possible" * would fail and only backtracking
finds the split that works.
Run
go test -v ./challenges/glob-matcher/go/
Sign in to submit your solution.