Frontend School

Transaction Description Pattern Matcher

DSA
hard

Transaction Description Pattern Matcher

Hard
String
Dynamic Programming
Greedy

Overview

Stripe processes millions of financial transactions daily. To ensure compliance, detect fraud, and categorize transactions, we often need to identify specific patterns within transaction descriptions. These patterns can sometimes be flexible, including wildcards to account for variations in merchant naming or product codes. Efficiently matching these patterns against large volumes of descriptions is critical for real-time processing and analysis.

What you need to do / Task

Implement a function matchTransactionPattern that determines if a given transactionDescription matches a pattern containing special wildcard characters.

The wildcard characters are:

  • ?: Matches any single character.
  • *: Matches any sequence of zero or more characters.

The match must cover the entire transactionDescription.

Input & output

function matchTransactionPattern(transactionDescription: string, pattern: string): boolean

  • transactionDescription: A string representing the text to be matched. It consists of lowercase English letters.
  • pattern: A string containing the pattern to match against. It can include lowercase English letters, and the wildcard characters ? and *.

Returns true if the transactionDescription matches the pattern completely, false otherwise.

Clarifications

  • An empty transactionDescription can match an empty pattern (e.g., "" matches "" is true).
  • An empty transactionDescription can match a pattern consisting only of * characters (e.g., "" matches "*" or "**" is true).
  • An empty pattern can only match an empty transactionDescription.

Examples

1

Example 1

Input:

transactionDescription = "adceb", pattern = "a*b"

Output:

true

Note:

The 'a' matches 'a'. The '*' matches the substring 'dce'. The 'b' matches 'b'. The entire transaction description is matched.

2

Example 2

Input:

transactionDescription = "acdcb", pattern = "a*c?b"

Output:

false

Note:

Despite various ways to interpret the wildcards, the pattern a*c?b cannot fully match acdcb. For example, if '*' matches 'cd', then 'c?b' needs to match 'cb'. 'c' matches 'c', '?' matches 'b', but then the pattern 'b' remains with nothing left in the description.

3

Example 3

Input:

transactionDescription = "abcde", pattern = "ace"

Output:

true

Note:

The 'a' matches 'a'. The first '' matches 'b'. The 'c' matches 'c'. The second '' matches 'd'. The 'e' matches 'e'. The entire transaction description is matched.

4

Example 4

Input:

transactionDescription = "", pattern = "*"

Output:

true

Note:

An empty string can be matched by a '*' wildcard (matching zero characters).

Constraints

Constraints & assumptions

  • 0 <= transactionDescription.length <= 2000
  • 0 <= pattern.length <= 2000
  • transactionDescription consists only of lowercase English letters.
  • pattern consists only of lowercase English letters, ?, or *.

Out of scope

  • Handling other regular expression metacharacters like +, {}, [], ^, $, etc.
  • Case-insensitivity or Unicode character support.
  • Finding all occurrences; only a full match is required.

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly handles all valid inputs and edge cases, including wildcards and empty strings.
  • Time and Space Complexity: The solution should be efficient, ideally achieving optimal or near-optimal time and space complexity for the given constraints.
  • Code Structure and Readability: The code is well-organized, easy to understand, and follows good programming practices.
  • Problem Decomposition: Ability to break down the problem into subproblems (e.g., using dynamic programming or a careful greedy approach).

Loading editor...