This problem is so difficult that I doubt life O (╥﹏╥)o

  1. Regular expression matching

Given a string s and a character rule P, implement a regular expression match that supports ‘.’ and ‘*’.

‘.’ matches any single character.’ *’ matches zero or more of the preceding elements.

Input: s = "aa" p = "a" Output: false Description: "A" cannot match the entire string "aa". Input: s = "aa" p = "a*" Output: true Thus, the string "aa" can be treated as 'a' repeated once. Input: s = "ab" p = ".*" Output: true Description: ".*" can match zero or more ('*') characters ('.').Copy the code

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Knowledge involved in Go includes:

  1. How to use two-dimensional arrays:
dp := make([][]bool, size)
Copy the code
  1. How to compare the characters of two strings in sequence: slicing. Considering the Chinese language, I think it should be used[]rune(s)And then compare.
s := "abc"
s[0] = ='a' // true
Copy the code
  1. String concatenation: In one solution, strings are cleverly concatenated to avoid array out-of-bounds problems.
s := "aaa"
b := s + "ddd"
Copy the code

A higher performance string concatenation method was found after reviewing the data:

var b bytes.Buffer
b.WriteString("aaa")
b.WriteString("bbv")
s := b.String()
Copy the code

In addition, a new Go language function declaration method learned from the official sample code, function within a function, like a variable declaration function:

func main(a) {
	// You can declare functions like variables
	inlineFunction := func(a) {
        fmt.Println("Hello")}// Function call
	inlineFunction()
}
Copy the code

The dynamic programming is a little bit complicated, and it took me a while to figure it out.

Just a dot and an asterisk can be so complex that the efficient implementation of complete re matching features in various languages is amazing! According to Effective Java, the most time-consuming part of regular expressions is the generation of finite state automata from regular expressions, so we can assume that finite-state automata is at least used for regular matching in Java.

Dynamic programming

Define state:

State transition equation:

In addition to the complex transfer equation, the initialization process is also more difficult to understand, empty string and empty string, empty string and the form of a* B * C *… The string also needs to be indicated in initialization. Another very clever way to avoid this process, which we won’t go into too much detail, is to add the same specific character to the head of both strings.

The implementation code is as follows:

func isMatch(s string, p string) bool {
	m, n := len(s), len(p)
	dp := make([] []bool, m + 1)
	for i := 0; i < len(dp); i ++ {
		dp[i] = make([]bool, n + 1)}// init
	dp[0] [0] = true
	// how to init 
	for j := 1; j < n+1; j++ {
		// fmt.Println(p[j-1])
		if p[j- 1] = =The '*' {
			// fmt.Println("j - 1 = ", j-1)
			dp[0][j] = dp[0][j2 -]}}// fmt.Println(dp)
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p[j- 1] = =The '*' {
				if j == 1 {
					// p begins with an asterisk (*). This is not the case
					dp[i][j] = false
				} else {
					if s[i- 1] == p[j2 -] || p[j2 -] = ='. ' {
						dp[i][j] = dp[i- 1][j] || dp[i][j2 -]}else {
						dp[i][j] = dp[i][j2 -]}}}else {
				if s[i- 1] == p[j- 1] || p[j- 1] = ='. ' {
					dp[i][j] = dp[i- 1][j- 1]}else {
					dp[i][j] = false}}// fmt.Println("d[", i, "][", j, "] = ", dp[i][j])}}return dp[m][n]

}
Copy the code

Because this problem delayed a lot of time, this week sent a little little blog, qingming holiday to catch up, O (╥﹏╥) O