题目链接
容我说一句，太抓狂了这题。太多太多的样例想不到。

思路

这道题我用了递归的方法，效率不高，但容易理解。这题难就难在对于 * 的处理，其他的都好说。
我的思路是：当读取模式串的一个字符后，若字符后面是 * 并且匹配成功后，分成三类处理：

  • 模式串后移两位，字符串不变
  • 模式串不变，字符串后移一位
  • 模式串后移两位，字符串后移一位

这样理解，当字符 a 与模式 a* 匹配成功后，该如何处理呢。因为 * 可匹配0个或多个，意味着
a*aaa 可以匹配 aaa , aaaa , aaaaa等等。 aaa 意味着 a* 匹配0个字符， aaaa 匹配1个字符。
即对于匹配成功的字符，不能确定是否要匹配，所以上面三条路都走一下。

代码

  1. fun isMatch(s: String, p: String): Boolean {
  2.     return isMatch(s, 0, p, 0)
  3. }
  5. fun isMatch(s: String, sIndex: Int, p: String, pIndex: Int): Boolean {
  6.     if (sIndex == s.length && pIndex == p.length) return true
  7.     if (pIndex == p.length) return false
  9.     return if (pIndex < p.length - 1) {
  11.         if (p[pIndex + 1] == '*') {
  12.             // 判一下字符串是否出界
  13.             if (sIndex == s.length) return isMatch(s, sIndex, p, pIndex + 2)
  15.             if (s[sIndex] == p[pIndex] || p[pIndex] == '.') {
  16.                 isMatch(s, sIndex + 1, p, pIndex) || isMatch(s, sIndex, p, pIndex + 2) || isMatch(s, sIndex + 1, p, pIndex + 2)
  17.             }else {
  18.                 isMatch(s, sIndex, p, pIndex + 2)
  19.             }
  20.         }else {
  21.             // 判一下字符串是否出界
  22.             if (sIndex == s.length) return false
  24.             if (s[sIndex] == p[pIndex] || p[pIndex] == '.') isMatch(s, sIndex+1, p, pIndex + 1)
  25.             else false
  26.         }
  27.     }else { // 模式到达末尾，若匹配成功且字符串也到达末尾，返回成功，否则失败
  28.         (sIndex == s.length - 1) && (s[sIndex] == p[pIndex] || p[pIndex] == '.')
  29.     }
  30. }