###### tags: `Leetcode` `hard` `dynamic programming` `python`

# 10. Regular Expression Matching

## [題目來源:] https://leetcode.com/problems/regular-expression-matching/

## 題目:
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).

## 解題想法:
' . ' 可以取代任何字符
' * ' 能將其前面的字符視為0orN個
重點考慮: 將' * '考慮為前一個字出現1次or0次

## Python (法1: DP):

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        m=len(s)
        n=len(p)
        #dp[i][j]: s[0:i+1]與p[0:j+1]是否匹配
        dp=[[False for _ in range(n+1)] for _ in range(m+1)]
        #init s、p皆空為True
        #當s為空 必須p為* 且將*視為前一個出現0次
        dp[0][0]=True 
        for i in range(1,n+1):
            if i>=2 and p[i-1]=='*':
                dp[0][i]=dp[0][i-2]
        #dp
        for i in range(1,m+1):
            for j in range(1,n+1):
                if j>=2 and p[j-1]=='*':
                    #case1: 將*考慮為前一個字出現1次 則p不動 但s跳過後一個字符
                    #case2: 將*考慮為前一個字出現0次 所以跳過*自己與前一個字符 p[2:]
                    dp[i][j]= dp[i][j-2] or (dp[i-1][j] and (s[i-1]==p[j-2] or p[j-2]=='.'))
                else:
                    dp[i][j]= dp[i-1][j-1] and ( s[i-1]==p[j-1] or p[j-1]=='.')
        return dp[m][n]
    
result=Solution()
ans=result.isMatch(s="mississippi",p=".*mis*is*ip*.")
print(ans)

## Python (法2: Recursive):

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        # '*'表示*前面的那個字符可以有0orN個
        #ex: a*b : 可以為 b or aaaaab
        #init
        if len(p)==0:
            return len(s)==0
        #比較s與p第一個字符是否相等
        if len(s)!=0 and (p[0]==s[0] or p[0]=='.'):
            cur_pos=True
        else:
            cur_pos=False
        #若p[1]=='*':兩種case:
        #case1: 將*考慮為前一個字出現1次 則p不動 但s跳過後一個字符
        #case2: 將*考慮為前一個字出現0次 所以跳過*自己與前一個字符 p[2:]
        if len(p)>=2 and p[1]=='*':
            return (cur_pos and self.isMatch(s[1:],p)) or (self.isMatch(s,p[2:]))
        else:
            return cur_pos and self.isMatch(s[1:],p[1:])
        
result=Solution()
ans=result.isMatch(s = "ab", p = ".*")
print(ans)