GuilinDev

Lc0010

05 August 2008

10 - Regular Expression Matching

原题概述

Given an input string (

1

s
) and a pattern (
1

p
), implement regular expression matching with support for 
1

'.'
and 
1

'*'
.

1
2

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

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

Note:

  • 1

    s
    could be empty and contains only lowercase letters 
    1

    a-z
    .
  • 1

    p
    could be empty and contains only lowercase letters 
    1

    a-z
    , and characters like 
    1

    .
    or 
    1

    *
    .

Example 1:

1
2
3
4
5

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

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".

Example 3:

1
2
3
4
5

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

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".

Example 5:

1
2
3
4

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

题意和分析

求两个字符串是否能完全cover。跟44-Wildcard Matching类似，*的意思略有不同，这道题*表示0个，1个或者多个前面的字符（包括’.’），因此a*b可以表示b，ab或aaab，即任意个a。

1）递归的办法，递归过程中的三种情况：

I - 如果p为空，s也为空，返回true，否则返回false，此为基线条件；

II - p和s不为空，且p的第二个字符为*，因为*之前的字符可以0个或任意正整数个，所以首先用递归调用*代表0的情况，也就是直接把*和它之前的这两个字符去掉再和s比较；而如果当s的第一个字符和p的第一个字符相同，或者p第一个字符等于‘.’（仅代表任意1个字符，可以认为.==s.charAt(0)），把s去掉首字符并递归检查。

III - p和s不为空，且递归过程中p的第二个字符不为*，那就如同正常字符串一样比较第一个字符，然后对后面的字符串调用递归。

2） DP的方法

如果能写成递归，基本就能改成动态规划，因为是两个字符串，这里需要声明一个二维数组布尔数组dp[i][j]

dp[i][j]：表示字符串中s中的前i个字符与字符串p中的前j个字符是否能够匹配。如果能匹配则为true，反之为false。

假如已经算出了前i-1个字符与前j-1个字符的匹配情况了，那如何计算dp[i][j]呢？

  • 如果s[i] == p[j]，说明dp[i][j]取决于dp[i-1][j-1]
  • 如果s[i] != p[j]，说明两个字符串不匹配

对于 ‘.’ 和 ‘*‘的处理

由于’.’ 和 ‘*‘都是在p中，所以

  • 当p[j] == ‘.’的时候，说明这个字符什么都可以当，和之前s[i] == p[j]是一样的，故dp[i][j] == dp[i - 1][j - 1].
  • 当p[j] == ‘*’ 的时候这要分两种情况：
    • 如果前面的字符p[j - 1]能与s当前的字符s[i]匹配上的话，那就dp[i][j]的状态就取决于dp[ i - 1][j]，也是就相当于看前面的状态。
    • 如果前面的字符p[j - 1]不能与s当前的字符s[i]匹配上的话，是不是就代表匹配失败了呢？不一定，因为这毕竟是一个 * 号而不是真正的要匹配的字符，说白了大不了不用它来匹配了，也就是使用0次，那就dp[i][j]的状态就去取决于dp[i][j - 2]。上面这两种状态只要能满足其中一种就可以了，即：

代码

递归

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.length() == 0) {
            return s.length() == 0;
        }
        if (p.length() > 1 && p.charAt(1) == '*') {
            return isMatch(s, p.substring(2)) || (s.length() != 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1), p));
        } else {
            return s.length() != 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1));
        }
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public boolean isMatch(String s, String p) {
        int lenS = s.length(), lenP = p.length();
        boolean[][] dp = new boolean[lenS + 1][lenP + 1]; //多一个初始状态，都为0的情况
        dp[0][0] = true;
        
        for (int j = 2; j <= lenP; j++) { // 先把"*"处理了
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        
        for (int i = 1; i <= lenS; i++) {
            for (int j = 1; j <= lenP; j++) {
                if (match(s.charAt(i - 1), p.charAt(j - 1))) { // 前面两个字符相匹配
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') { // p中前面一个字符为'*'，分两种情况
                    dp[i][j] = dp[i][j - 2]; // 情况1
                    if (match(s.charAt(i - 1), p.charAt(j - 2))) { // 情况2
                        dp[i][j] |= dp[i - 1][j]; // |=表示可能dp[i][j]之前'*'处理过
                    }
                }
            }
        }
        return dp[lenS][lenP];
    }
    private boolean match(char a, char b) {
        return a == b || b == '.';
    }
}
This site is open source. Improve this page.