正则表达式匹配——基于字符串的高级动静布局 / 回溯 / 自动机
1
动静布局
// 不是很懂,等刷动静布局的时候再来二刷
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)著作权归作者所有。商业转载请分割作者取得受权,非商业转载请注明出处。