算法题——字符串3.19 leetcode

正则表达式匹配——基于字符串的高级动态规划/回溯/自动机 1
动态规划
//不是很懂，等刷动态规划的时候再来二刷
【算法题——字符串3.19】https://leetcode-cn.com/probl...
//这个好像讲得比官解好一些

func isMatch(s string, p string) bool { m, n := len(s), len(p) matches := func(i, j int) bool { if i == 0 { return false } if p[j-1] == '.' { return true } return s[i-1] == p[j-1] }f := make([][]bool, m + 1) for i := 0; i < len(f); i++ { f[i] = make([]bool, n + 1) } f[0][0] = true for i := 0; i <= m; i++ { for j := 1; j <= n; j++ { if p[j-1] == '*' { f[i][j] = f[i][j] || f[i][j-2] if matches(i, j - 1) { f[i][j] = f[i][j] || f[i-1][j] } } else if matches(i, j) { f[i][j] = f[i][j] || f[i-1][j-1] } } } return f[m][n] }作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode-solution/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2
递归
https://leetcode-cn.com/probl...
3

文章图片

4.回溯...
表示数值的字符串常规
strings包的常见函数
https://blog.csdn.net/liukai6...8
具体实现

func isNumber(s string) bool { // 掐头去尾--> 去掉开始和结束的空格 i, j := 0, len(s)-1 for ; i < len(s); i++ { if s[i] != ' ' { break } } for ; j >= 0; j-- { if s[j] != ' ' { break } } if j+1 <= i { return false } s = s[i : j+1] // 判断是否有科学计数法 if (strings.Count(s,"e")+ strings.Count(s,"E"))>1{ return false } science := max(max(-1, strings.Index(s, "e")), strings.Index(s, "E")) if science == -1 { return isInteger(s) || isDecimal(s) } else { return (isInteger(s[:science]) || isDecimal(s[:science])) && isInteger(s[science+1:]) } }func max(a, b int) int { if a > b { return a } return b }// 判断是不是整数 func isInteger(s string) bool { if len(s) == 0 { return false } i := 0 if s[0] == '+' || s[0] == '-' { if len(s) == 1 { return false } i = 1 } for ; i < len(s); i++ { if s[i] < '0' || s[i] > '9' { return false } }return true }// 判断是不是小数 func isDecimal(s string) bool { if strings.Count(s, ".") != 1 || len(s) == 0 { return false } i := 0 if s[0] == '+' || s[0] == '-' { if len(s) == 1 { return false } i++ } index := strings.Index(s, ".") left, right := 0, 0 for ; i < index; i++ { if s[i] < '0' || s[i] > '9' { return false } left++ } for i++; i < len(s); i++ { if s[i] < '0' || s[i] > '9' { return false } right++ } return left >= 1 || (left == 0 && right > 0) }

进阶
自动机-官解
https://leetcode-cn.com/probl...
正则表达式

func isNumber(s string) bool { ret,_ := regexp.MatchString(`^\s*[+-]?((\d*\.\d+)|(\d+\.?\d*))([eE][+-]?\d+)?\s*$`,s); //ret,v := regexp.Match("\d+",[]byte(s)); //ret := reg.MatchString(s) //fmt.Println(ret) return ret }作者：flytotoro 链接：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/solution/go-zheng-ze-biao-da-shi-by-flytotoro-9jph/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。