/10. Regular Expression Matching
Previous|Next

10. Regular Expression Matching

Hard
Strings30.6% acceptance

Given two strings, input_string and pattern_string, determine if pattern_string matches the entire input_string. The pattern_string may contain the special characters . (matches any single character) and * (matches zero or more of the preceding element). Return True if the pattern matches the entire input_string, otherwise return False.

Example 1

Input: input_string=abc, pattern_string=a.c

Output: True

Explanation: . matches b, so a.c matches abc.

Example 2

Input: input_string=aab, pattern_string=c*a*b

Output: True

Explanation: c* matches zero c, a* matches two a, b matches b.

Example 3

Input: input_string=abcd, pattern_string=.*d

Output: True

Explanation: .* matches abc, d matches d.

Example 4

Input: input_string=miss, pattern_string=mis*

Output: True

Explanation: s* matches two s.

Example 5

Input: input_string=abc, pattern_string=ab*

Output: False

Explanation: b* matches one or more b, but there is only one b and no c in the pattern.

Constraints

  • 1 <= len(input_string) <= 20
  • 1 <= len(pattern_string) <= 20
  • input_string consists only of lowercase English letters
  • pattern_string consists only of lowercase English letters, ., and *
  • Every * in pattern_string is preceded by a valid character
Python (current runtime)

Case 1

Input: input_string='bba', pattern_string='b*a'

Expected: True

Case 2

Input: input_string='xyz', pattern_string='x.*z'

Expected: True

Case 3

Input: input_string='a', pattern_string='ab*'

Expected: True

Case 4

Input: input_string='aabb', pattern_string='a*b*'

Expected: True

Case 5

Input: input_string='abc', pattern_string='a.*d'

Expected: False