Regular Expression Matching go语言

Regular Expression Matching

题目描述

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 *.

思路：

• *匹配前面字符的重复。动态规划匹配串，和模式串索引。记录匹配串和模式串，所有从0开始的子串的匹配。总长度dp[s+1]][p+1]。最小问题为，从匹配0个字符开始填，第一行容易填。
• p[j]为.或匹配了s[i] 则dp[i][j] = dp[i-1][j-1]
• p[j]为*：
  • a*空匹配，dp[i][j] = dp[i][j-2]
  • 为.*或者匹配，以下3情况，有一种情况匹配，则匹配：
    • 多匹配：dp[i][j] = d[i-1][j]。（只是去掉s中的一个匹配字符，并未清掉a*对应的所有匹配）
    • 单匹配：dp[i][j] = dp[i-1][j-2]（或者是dp[i][j-1]）
• 由以上递推关系，需要先将i=0行填好，再补上。匹配一个字符，模式会有多个a*。

细节：

• 防止取j-1时数组越界。
• p[j]为*，且p[j-1]匹配或不匹配时，a*匹配0个字符并不是同一种情况，因而都会有dp[i+1][j-1]的选项。

解：

package main

import "fmt"

func isMatch(s string, p string) bool {
    sSlice := []rune(s)
    pSlice := []rune(p)
    dp := make([][]bool,len(s)+1)
    for idx,_ := range dp{
        dp[idx] = make([]bool,len(p)+1)
    }
    dp[0][0] = true
    for i:=0;i<len(p);i++ {
        if pSlice[i] == '*' {
            dp[0][i+1] = dp[0][i-1]
        }
    }
    for i:=0;i<len(s);i++{
        for j:=0;j<len(p);j++{
            if  pSlice[j] == '.' || pSlice[j] == sSlice[i]{
                dp[i+1][j+1] = dp[i][j]
            }
            if pSlice[j] == '*'{
                if pSlice[j-1] == '.' || pSlice[j-1] == sSlice[i]{
                    //a*匹配1个或多个
                    dp[i+1][j+1] = dp[i+1][j]|| dp[i][j+1]||dp[i+1][j-1]
                }else if j>0 {
                    dp[i+1][j+1] = dp[i+1][j-1]
                }
            }
        }
    }
    return dp[len(s)][len(p)]
}

func main()  {
    s := ""
    p := ".*"
    res := isMatch(s, p)
    fmt.Print(res)
}