LeetCode--Regular Expression Matching

发表于 | 分类于 |

题目描述：

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.'and '*'.

1
2
'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

样例：

1
2
3
4
5
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
1
2
3
4
5
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
1
2
3
4
5
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
1
2
3
4
5
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
1
2
3
4
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

题意：

给出一个字符串 s和一个匹配串 p,并且匹配串中会有.和*，其中.和*分别代表：

1
2
'.' 匹配任何单个字符。
'*' 匹配前面元素的零个或多个。

思路：

蚊子的思路就是先将简单的情况列举出来进行判断，然后再将复杂的情况分割成简单的情况，然后逐一递归破解。

  1. 若p为空，且s也为空，返回 true，反之返回 false。
  2. 若p的长度为 1，且s长度也为 1，且相同或者p为 ‘.’ 则返回 true，反之返回 false。
  3. 若p的第二个字符不为 ‘*’，若此时s为空，返回 false，否则判断首字符是否匹配，然后调用各自的第二个字符进行递归判断。
  4. 若p的第二个字符为 ‘*’，进行下列循环，若s不为空，且首字母匹配，调用递归函数判断s和去掉前两个字符的串p（这样做的原因是假设此时的型号的作用是让前面的字符出现 0 次，验证是否匹配）若匹配，返回 true，否则s去掉首字母（因为此时首字母匹配了，我们可以去掉s的首字母，而p由于星号的作用，可以有任意个首字母，所以不需要去掉），然后继续循环。
  5. 最后一种是处理 ‘*‘ 无法匹配的情况（比如 s = “ab”，p = “a*b”，直接进入第四种情况后，我们会发现 “ab” 和 “b” 不匹配，所以s变成 “b”，那么此时跳出循环后，就到最后的比较 “b” 和 “b” 了，最后返回 true）

最后蚊子的代码是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isMatch(string s, string p) {
        if(p.empty()) return s.empty();
        if(p.size() == 1) return (s.size() == 1 && (s[0] == p[0] || p[0] =='.'));
        if(p[1] != '*'){
            if(s.empty()) return false;
            return (s[0] == p[0] || p[0] =='.') && isMatch(s.substr(1), p.substr(1));
        }
        while(!s.empty() && (s[0] == p[0] || p[0] =='.')){
            if(isMatch(s, p.substr(2))) return true;
            s = s.substr(1);
        }
        return isMatch(s, p.substr(2));
    }
};

Rumtime：200ms Memory：14.5MB

然后发现讨论区的同伴们真的强，这代码也太简洁了叭，tql

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) return s.empty();
        if (p.size() > 1 && p[1] == '*') {
            return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p));
        } else {
            return !s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
        }
    }
};

Rumtime：224ms Memory：18.1MB