GeetCode Hub

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*' where: 

  • '.' Matches any single character.​​​​
  • '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

 

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

Input: s = "mississippi", p = "mis*is*p*."
Output: false

 

Constraints:

  • 0 <= s.length <= 20
  • 0 <= p.length <= 30
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.
  • It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

class Solution: def __init__(self): self.cache={} # use (len_s, len_p) as key def cache_match(self,s,p,tab): # print('\t'*tab+" cache_match:{} <==> {}".format(s,p)) key=(len(s), len(p)) if key in self.cache: return self.cache[key] result = self.isMatch(s,p,tab) self.cache[key]=result return result def isMatch(self, s: str, p: str, tab=0) -> bool: # print('\t'*tab+"try match:{} & {}".format(s,p)) while len(p)>0: # print('\t'*tab+"match:{} & {}".format(s,p)) c=p[0] nextc = p[1] if len(p)>1 else None if nextc!='*': if not s or (c!='.' and s[0]!=c): return False p=p[1:] s=s[1:] else: # nextc=='*' # print('\t'*tab+"*****************") if self.cache_match(s,p[2:], tab+1): return True for i in range(len(s)): # print('\t'*tab+"_______ {} ________".format(i)) if c=='.' or c==s[i]: if self.cache_match(s[i+1:],p[2:],tab+1): return True else: return False return False return not s

This is one of the top questions we should be solving in Dynamic Programming. The basic idea is to break the bigger task into smaller tasks and keep track of already solved tasks and re-use the result.

Time Complexity: O(m*n) // where m and n are the lengths of string and patterns

Space Complexity: O(m*n)