这段时间刷了刷letcode,编程的乐趣可能就是`它就在那儿,而你要征服它`(哈哈哈),刷过一道题时,会有种莫名其妙的快感!
可以匹配任何单个字符。
'*' 可以匹配任意字符串(包括空字符串)。
示例:(抄自 letcode)
输入:s = "aa"p = "a"输出: false解释: "a" 无法匹配 "aa" 整个字符串。输入:s = "aa"p = "*"输出: true解释: '*' 可以匹配任意字符串。输入:s = "cb"p = "?a"输出: false解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。输入:s = "adceb"p = "*a*b"输出: true解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".输入:s = "acdcb"p = "a*c?b"输入: false
*匹配的字符串具有不确定性,但是我们只要找出一种成功pattern匹配str的可能即可,并不一定需要遍历所有可能(剪枝);
?相比*只占一个字符的空间(确定的),所以任何一个字符(这里的字符指[a-zA-Z0-9_])都可以匹配?;而任意字符串都能匹配*(包括空字符串),(了解正则的同学应该知道贪婪匹配和懒惰匹配,先列出这两个名词,稍后在算法中会有体现) ;
如果pattern中包含*, 在不确定*应该匹配哪一子串的情况下,需要遍历每一种可能的情况,直到找到解,需要回溯;如果pattern不包含*,则只需要比较pattern和str上对应位置的字符,而?可以和任一字符匹配,不需要回溯。
pattern中包含*的匹配流程图例:(以懒惰匹配举例,展示核心算法)
然而通过构造特殊的pattern和str,该流程的计算时间将会指数级增加(有关正则表达式注入请了解一下);所以需要对pattern进行优化并剪去不可能的分支。
先展示一下我的提交列表(前前后后共进行了5次优化)
v0.1 版本
func sMatch(pattern, str []rune) bool { if len(str) <= 0 { if len(pattern) <= 0 { return true } for _, c := range pattern { if c != '*' { return false } } return true } if len(pattern) <= 0 { return false } sl := len(str) pIndex := 0 i := 0 for i = 0; i < sl; i { if pIndex >= len(pattern) { break } switch pattern[pIndex] { case '*': gl := sl flag := false for gl >= i && gl >= 0{ if sMatch(pattern[pIndex 1:], str[gl:]) { flag = true break } gl-- //丢弃一个 } return flag case '?': pIndex default: if str[i] != pattern[pIndex] { return false } pIndex } } if i == len(str) && pIndex != len(pattern) { for i := pIndex; i < len(pattern); i { if pattern[i] != '*' { return false } } return true } if pIndex != len(pattern) || i != len(str) { return false } return true}func isMatch(s string, p string) bool { if len(s) <= 0 { if len(p) <= 0 { return true } for _, c := range p { if c != '*' { return false } } return true } if len(p) <= 0 { return false } return sMatch([]rune(p), []rune(s))}
死在了这个case上:
str: "bbbababbbbabbbbababbaaabbaababbbaabbbaaaabbbaaaabb"pattern: "*b********bb*b*bbbbb*ba"
v0.1 以贪婪匹配规则回溯的,然后将算法改为以懒惰匹配规则回溯,成功通过这个case
v0.2版本
```省略 case '*': gl := i flag := false for gl < sl{ if pIndex == len(pattern)-1 { return true } if sMatch(pattern[pIndex 1:], str[gl:]) { flag = true break } gl //要一个 } return flag```省略
然而又死在了这个case上:
str: "aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba"pattern: "*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*"
突然,我想到相连的多个*不就等于单个* (a** <=> a* 一个道理)
v0.3版本
``` 省略 nPattern := make([]rune, 0, len(p)) flag := false for _, v := range p { if v == '*' && flag { continue } if v == '*' { flag = true } else { flag = false } nPattern = append(nPattern, v) } return sMatch(nPattern, []rune(s))```省略
想着这回应该OK了吧(真是有够折磨人的,多亏了好case不然就没有下面的优化了)
case: 这里改一下,timeout了(啥!!!!)
str: "abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb"pattern: "**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"
终于我又发现(我其实一开始就知道,只是不知道如何表现),pattern中非*的子串必定存在于str中,不然必定匹配失败!
v0.4版本 诞生
func prepareMatch(pattern, str string) bool { p1 := strings.Replace(pattern, "?", "*", len(pattern)) p2 := strings.Split(p1, "*") if len(p2) > 1 { for _, v := range p2 { if v == "" { continue } if strings.Count(p1, v) > strings.Count(str, v) { return false } } } return true}```省略 if !prepareMatch(p, s) { return false } return sMatch(nPattern, []rune(s))```省略
其实这一版的优化有点小瑕疵,优化的大概意思是pattern中非*?的子串出现的次数应该等于它们在str中出现的次数,但是我忽略了它们之前的出现顺序,所以又一个case让我timeout了
str: "aaaaaabbaabaaaaabababbabbaababbaabaababaaaaabaaaabaaaabababbbabbbbaabbababbbbababbaaababbbabbbaaaaaaabbaabbbbababbabbaaabababaaaabaaabaaabbbbbabaaabbbaabbbbbbbaabaaababaaaababbbbbaabaaabbabaabbaabbaaaaba"pattern: "*bbb**a*******abb*b**a**bbbbaab*b*aaba*a*b**a*abb*aa****b*bb**abbbb*b**bbbabaa*b**ba**a**ba**b*a*a**aaa"
不知道看到这个case的各位,有没有发现pattern和str的末尾字串并不匹配,但是因为匹配顺序是从前往后,即使最终匹配失败,程序还是会傻呼呼的尝试完所有可能,因此v0.5终于诞生了(顺便修复了v0.4版本的小瑕疵)。
v0.5版本(终焉版本)
func prepareMatch(pattern, str string) bool { p1 := strings.Replace(pattern, "?", "*", len(pattern)) p2 := strings.Split(p1, "*") cs := str //第一步预处理 if len(p2) > 1 { for _, v := range p2 { if v == "" { continue } if i := strings.Index(cs, v); i < 0 { return false } else { cs = cs[i len(v):] } } } //第二步预处理 if pattern[len(pattern)-1] != '*' && len(p2) > 2{ if !strings.HasSuffix(str, p2[len(p2)-1]) { return false; } } return true}
优化了v0.4出现的两个问题
编程的乐趣可能还是 不断解决程序运行的问题 的过程!
完整终焉版本
import "strings"func sMatch(pattern, str []rune) bool { if len(str) <= 0 { if len(pattern) <= 0 { return true } for _, c := range pattern { if c != '*' { return false } } return true } if len(pattern) <= 0 { return false } sl := len(str) pIndex := 0 i := 0 for i = 0; i < sl; i { if pIndex >= len(pattern) { break } switch pattern[pIndex] { case '*': gl := i flag := false for gl < sl{ if pIndex == len(pattern)-1 { return true } if sMatch(pattern[pIndex 1:], str[gl:]) { flag = true break } gl //要一个 } return flag case '?': pIndex default: if str[i] != pattern[pIndex] { return false } pIndex } } if i == len(str) && pIndex != len(pattern) { for i := pIndex; i < len(pattern); i { if pattern[i] != '*' { return false } } return true } if pIndex != len(pattern) || i != len(str) { return false } return true}//优化func prepareMatch(pattern, str string) bool { p1 := strings.Replace(pattern, "?", "*", len(pattern)) p2 := strings.Split(p1, "*") cs := str //第一步预处理 if len(p2) > 1 { for _, v := range p2 { if v == "" { continue } if i := strings.Index(cs, v); i < 0 { return false } else { cs = cs[i len(v):] } } } //第二步预处理 if pattern[len(pattern)-1] != '*' && len(p2) > 2{ if !strings.HasSuffix(str, p2[len(p2)-1]) { return false; } } return true}func isMatch(s string, p string) bool { if len(s) <= 0 { if len(p) <= 0 { return true } for _, c := range p { if c != '*' { return false } } return true } if len(p) <= 0 { return false } nPattern := make([]rune, 0, len(p)) flag := false for _, v := range p { if v == '*' && flag { continue } if v == '*' { flag = true } else { flag = false } nPattern = append(nPattern, v) } if !prepareMatch(p, s) { return false } return sMatch(nPattern, []rune(s))
联系客服