FastPrep
Problem · String

Generate Pattern Matching Strings (Early Career :)

Learn this problem
● MediumGoogleNEW GRADPHONE SCREEN
See Google hiring insights

Problem statement

You are given a pattern consisting of alpha characters and [] (square brackets). Anything outside of [] is literal, anything inside [] are alternatives (pick exactly one). Return all strings from a list of strings that match a given pattern. The pattern changes for every call, the list of strings stays the same and can be preprocessed.

Function

generatePatternMatchingStrings(pattern: String, strings: List<String>) → List<String>

Examples

Example 1

pattern = "tele[op]ho[bnm]e"strings = ["cat", "dog", "telephone", "telephonepole", "tele", "telehoe", "teleophobme"]return = ["telephone"]
:O

Constraints

  • 1 ≤ pattern.length ≤ 10^5
  • 0 ≤ strings.length ≤ 10^5
  • The total length of all strings is at most 10^6.
  • The pattern contains alphabetic literals and well-formed, non-empty square-bracket groups. Each bracket group contributes exactly one character to a match.
  • Return matching strings in their original input order.

More Google problems

drafts saved locally
public List<String> generatePatternMatchingStrings(String pattern, List<String> strings) {
  // write your code here
}
pattern"tele[op]ho[bnm]e"
strings["cat", "dog", "telephone", "telephonepole", "tele", "telehoe", "teleophobme"]
expected["telephone"]
checking account