FastPrepMatch File Paths with Wildcards

Match File Paths with Wildcards

Google logoGoogle● MediumINTERNONSITE INTERVIEW
Learn

Problem statement

You are given an array of unique canonical absolute file paths and an absolute wildcard pattern. Return every file path that matches the entire pattern.

Pattern rules

  • A slash separates path segments.
  • Literal characters match case-sensitively.
  • Inside one segment, * matches any sequence of zero or more non-slash characters.
  • A run of stars inside a segment behaves as one * unless the complete segment is exactly **.
  • A complete pattern segment equal to ** matches zero or more complete path segments.

Return each matching input path once, sorted in lexicographic order. A partial prefix or suffix match is not sufficient.

Function

matchFilePaths(filePaths: String[], pattern: String) → String[]

Examples

Example 1

filePaths = ["/home/a.txt","/home/user/docs/a.txt","/home/user/docs/b.txt","/var/log/a.txt"]pattern = "/home/**/a.txt"return = ["/home/a.txt","/home/user/docs/a.txt"]

The ** segment first matches zero directory segments and then matches user/docs. Paths outside /home and files with another final name do not match.

Example 2

filePaths = ["/home/user/docs/a.txt","/home/user/images/a.png","/home/admin/docs/a.txt","/var/log/app.log"]pattern = "/home/*/docs/a.txt"return = ["/home/admin/docs/a.txt","/home/user/docs/a.txt"]

The single-star segment matches exactly one directory level. Both matching paths are returned in lexicographic order even though the input order is different.

Example 3

filePaths = ["/a/file.txt","/a/fe.txt","/a/fee.txt","/a/folder/file.txt"]pattern = "/a/f**e.txt"return = ["/a/fe.txt","/a/fee.txt","/a/file.txt"]

Because the repeated stars occur inside a larger segment, they act as one segment-local wildcard. That wildcard may match an empty string, but it never crosses a slash.

Constraints

  • 1 <= filePaths.length <= 5000
  • 1 <= pattern.length <= 200
  • Every path and the pattern begin with /, have no trailing slash, and contain no empty, ., or .. segment.
  • File-path segments contain letters, digits, dots, underscores, and hyphens. Pattern segments may additionally contain *.
  • The total number of characters across filePaths is at most 200000.

More Google problems

See Google hiring insights
public String[] matchFilePaths(String[] filePaths, String pattern) {
    // Write your code here.
}
filePaths["/home/a.txt","/home/user/docs/a.txt","/home/user/docs/b.txt","/var/log/a.txt"]
pattern"/home/**/a.txt"
expected["/home/a.txt", "/home/user/docs/a.txt"]
Checking account…