龙

哇咔咔

0%

LeetCode 10 Regular Expression Matching

发表于 分类于 Disqus：
Leetcode第10题，字符串匹配问题。

Description:

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

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

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a*“) → true
isMatch(“aa”, “.*“) → true
isMatch(“ab”, “.*“) → true
isMatch(“aab”, “c*a*b”) → true

题目理解：给两个字符串，用第二个字符串去匹配第一个字符串，意思就是第一个字符串中的字符不转义， 只有第二个字符串才需要转义。

需要注意的是，一个字符后面如果跟上*，那么这个字符一定要转义，也就是例如a*与a*不能匹配，因为第一个a*不转义， 第二个a*转义，所以第一个a*中的*将匹配不上。

思路：几个月之前，显然不知道动态规划，就直接递归，非常二。当然也能击败一半人…

刚看了动态规划，这个问题典型的动态规划问题，使用自顶向下的策略，速度得到提升。

代码一：直接递归版本

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Solution {
    public boolean isMatch(String s, String p) {
        char[] s_array = s.toCharArray();
        char[] p_array = p.toCharArray();
        
        int si = 0;
        int pi = 0;
        while (  pi < p_array.length ) {
            if ( pi + 1 != p_array.length && p_array[ pi + 1 ] == '*' ) {
                int si_back = s_array.length - 1;
                int pi_back = p_array.length - 1;
                while ( pi_back > pi + 1 && si_back >= si ) {
                    if ( p_array[pi_back] == '*' )
                        break;
                    if ( p_array[pi_back] != s_array[si_back] && p_array[pi_back] != '.' ) 
                        return false;
                    pi_back--;
                    si_back--;
                }
                pi_back++;
                si_back++;
                String p_sub = p.substring( pi + 2 , pi_back );
                if ( p_array[pi] == '.' ) {
                    while ( si <= si_back ) {
                        if ( isMatch( s.substring( si , si_back ) , p_sub ) )
                            return true;
                        si++;
                    }
                    return false;
                } else {
                    while ( si < si_back && s_array[si] == p_array[pi] ) {
                        if ( isMatch( s.substring( si , si_back ) , p_sub ) )
                            return true;
                        si++;
                    }
                    return isMatch( s.substring( si , si_back ) , p_sub );
                }
            } else {
                if ( p_array[pi] == '.' ) {
                    if ( si == s_array.length ) 
                        return false;
                    pi++;
                    si++;
                } else {
                    if ( si == s_array.length || s_array[si] != p_array[pi] ) 
                        return false;
                    pi++;
                    si++;
                }
            }
        }
        return si == s_array.length;
    }
}

复杂度：指数级别。
运行时间：33ms。
击败：44.25%。

image

代码二：动态规划（自顶向下）

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Solution {
    public boolean isMatch(String s, String p) {
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        char[][] matchs = new char[ss.length + 1][pp.length + 1];
        for ( int i = 0; i < ss.length; i++ )
            matchs[i][pp.length] = '0';
        matchs[ss.length][pp.length] = '1';
        return myMatch( matchs, ss, pp, 0, 0) == '1';
    }
    
    private char myMatch( char[][] matchs, char[] s, char[] p, int si, int pi ) {
        if ( matchs[si][pi] == '1' || matchs[si][pi] == '0' )
            return matchs[si][pi];
        if ( pi + 1 < p.length && p[pi + 1] == '*' ) {
            matchs[si][pi] = myMatch( matchs, s, p, si, pi + 2 );
            if ( matchs[si][pi] == '1' )
                return matchs[si][pi];
            if ( p[pi] == '.' ) {
                for ( int i = si + 1; i <= s.length; i++ ) {
                    matchs[si][pi] = myMatch( matchs, s, p, i, pi + 2 );
                    if ( matchs[si][pi] == '1' )
                        return matchs[si][pi];
                }
            } else {
                int i = si;
                while ( i < s.length && s[i] == p[pi] ) {
                    matchs[si][pi] = myMatch( matchs, s, p, i + 1, pi + 2 );
                    if ( matchs[si][pi] == '1' )
                        return matchs[si][pi];
                    i++;
                }
            }   
        } else if ( p[pi] == '.' ) {
            if ( si == s.length )
                matchs[si][pi] = '0';
            else 
                matchs[si][pi] = myMatch( matchs, s, p, si + 1, pi + 1 );
        } else {
            if ( si == s.length || s[si] != p[pi] )
                matchs[si][pi] = '0';
            else 
                matchs[si][pi] = myMatch( matchs, s, p, si + 1, pi + 1 );
        }
        return matchs[si][pi];
    }  
}

复杂度：O(n^2)???
运行时间：25ms。
击败：99.48%

image