10. Regular Expression Matching

Description

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

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

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

Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.

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 precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

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

Example 4:

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

Example 5:

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

Tags: Math, String

题意

根据要求匹配字符

题解

思路1

用dp, ```go func isMatch(s string, p string) bool { // DP解法 dp := make([][]bool, len(s)+1) for i:=0; i<len(s)+1; i++ { dp[i] = make([]bool, len(p)+1) } dp[len(s)][len(p)] = true

for i:=len(s); i>=0; i--{
    for j:=len(p)-1; j>=0; j--{
        // 检查每个匹配的第一个字母是否匹配
        fm := false
        if i<len(s) && (s[i]==p[j] || p[j]=='.') {
            fm = true
        }

        // 当第二个字符模式中有*时
        if (j+1)<len(p) && p[j+1]=='*' {
            // 考虑*为0并且重合
            // 如果不匹配,检查第一个匹配是否与[i + 1,j]匹配
            dp[i][j] = dp[i][j+2] || (fm && dp[i+1][j])
            //fmt.Println("a",i,j,dp[i][j])
        }else{
            dp[i][j] = fm && dp[i+1][j+1]
            //fmt.Println("b",i,j,dp[i][j])
        }
    }
}
return dp[0][0]

}


### 思路2
> 思路2
```go

结语

如果你同我一样热爱数据结构、算法、LeetCode,可以关注我 GitHub 上的 LeetCode 题解:awesome-golang-leetcode

results matching ""

    No results matching ""