Golang正则匹配

题目

用 Golang 实现给你一个 字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例1

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例2

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例3

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例4

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例5

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

代码具体实现

package main
import (
	"fmt"
)
func isMatch2(s string, p string) bool {
	return compare(s, split(p))
}
type regType struct {
	// 0: 纯字符串
	// 1：字母*
	// 2： .
	// 3: .*
	regType int
	value string
}
func split(p string) []regType {
	var arr []regType
	preIndex := 0
	for i := 0; i < len(p); i++ {
		// 字母*
		if p[i] == '*' && i-1 >= 0 && p[i-1] != '.' {
			if i+2 < len(p) && p[i-1] == p[i+1] && p[i+2] == '*' {
				rs := []rune(p)
				rs = append(rs[:i+1], rs[i+3:]...)
				p = string(rs)
				i = preIndex
				continue
			}
			if i-2 >= 0 && p[i-2] >= 'a' && p[i-2] <= 'z' {
				arr = append(arr, regType{regType: 0, value: string(p[preIndex : i-1])})
				arr = append(arr, regType{regType: 1, value: string(p[i-1])})
			} else {
				arr = append(arr, regType{regType: 1, value: string(p[i-1])})
			}
			preIndex = i + 1
		}
		// .
		if p[i] == '.' && i+1 < len(p) && p[i+1] != '*' {
			if i-1 >= 0 && p[i-1] >= 'a' && p[i-1] <= 'z' {
				arr = append(arr, regType{regType: 0, value: string(p[preIndex:i])})
			}
			arr = append(arr, regType{regType: 2})
			preIndex = i + 1
		} else if p[i] == '.' && i+1 >= len(p) {
			if i-1 >= 0 && p[i-1] >= 'a' && p[i-1] <= 'z' {
				arr = append(arr, regType{regType: 0, value: string(p[preIndex:i])})
			}
			arr = append(arr, regType{regType: 2})
			preIndex = i + 1
		}
		// .*
		if i-1 >= 0 && p[i-1] == '.' && p[i] == '*' {
			if i-2 >= 0 && p[i-2] >= 'a' && p[i-2] <= 'z' {
				arr = append(arr, regType{regType: 0, value: string(p[preIndex : i-1])})
			}
			arr = append(arr, regType{regType: 3})
			preIndex = i + 1
		}
	}
	if preIndex < len(p) {
		arr = append(arr, regType{regType: 0, value: string(p[preIndex:])})
	}
	return arr
}
func compare(s string, arr []regType) bool {
	index := 0
	vIndex := 0
	for i := 0; i < len(arr); i++ {
		item := arr[i]
		switch item.regType {
		case 0:
			if index == len(s) {
				return false
			}
			if len(s) >= index+len(item.value) && item.value == s[index:index+len(item.value)] {
				index = index + len(item.value)
			} else {
				return false
			}
		case 1:
			for ; index < len(s); index++ {
				if string(s[index]) != item.value {
					break
				}
				vIndex++
			}
			if vIndex > 0 {
				for k := index - vIndex; k < len(s) && vIndex >= 0; {
					if !compare(s[k:], arr[i+1:]) {
						k++
					} else {
						return true
					}
					vIndex--
				}
			}
		case 2:
			if index == len(s) {
				return false
			}
			index++
		case 3:
			if i == len(arr)-1 {
				index = len(s)
			} else {
				vIndex = len(s) - index
				endFlag := true
				for _, item := range arr[i:] {
					if item.regType == 0 || item.regType == 2 {
						endFlag = false
					}
				}
				if endFlag {
					return true
				}
				for k := index; index < len(s) && vIndex > 0; {
					if k < len(s) && !compare(s[k:], arr[i+1:]) {
						k++
					} else {
						return true
					}
					vIndex--
				}
			}
		}
	}
	if index < len(s) {
		return false
	} else {
		return true
	}
}
//方法 1：回溯
func isMatch(s string, p string) bool {
	if p == "" {
		return len(s) == 0
	}
	firstMatch := s != "" && (p[0] == '.' || s[0] == p[0])
	if len(p) >= 2 && p[1] == '*' {
		//fmt.Println(p[2:])
		return isMatch(s, p[2:]) || (firstMatch && isMatch(s[1:], p))
	} else {
		return firstMatch && isMatch(s[1:], p[1:])
	}
	return true
}
func main() {
	fmt.Println("嗨客网(www.haicoder.net)")
	fmt.Println(isMatch("aa", "a"))
	fmt.Println(isMatch("aa", "a*"))
	fmt.Println(isMatch("ab", ".*"))
	fmt.Println(isMatch("aab", "c*a*b"))
	fmt.Println(isMatch("mississippi", "mis*is*p*."))
}

程序运行后，控制台输出如下：

我们输入了五个测试用例，都输出了正确结果。