这段时间刷了刷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))联系客服
