乐趣区

关于leetcode:算法题字符串319

jiezi

正则表达式匹配——基于字符串的高级动静布局 / 回溯 / 自动机

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）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。
退出移动版