Regular Expression Matching

Description

Implement regular expression matching with support for ‘.’ and ‘*‘.

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

简单的字符匹配

Solution

 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
func isMatch(s string, p string) bool {
    if len(s) == 0 && len(p) == 0 {
        return true
    } else if len(p) == 0 {
        // p is empty but s
        return false
    }

    matchChar := p[0]

    if len(p) > 1 && p[1] == '*' {
        // match any numbers of char(s)

        // eat two char of p
        p = p[2:]

        for len(s) > 0{
            if s[0] == matchChar || matchChar == '.' {
                // try not to eat char of s
                if isMatch(s, p) {
                    return true
                }

                // let's eat one char of s and try again
                s = s[1:]
            } else {
                break
            }
        }
    } else {
        // match one char

        // eat one char of p
        p = p[1:]

        // does it match?
        if len(s) == 0 || (s[0] != matchChar && matchChar != '.') {
            return false
        }

        // eat one char of s
        s = s[1:]
    }

    return isMatch(s, p)
}

Similar Problem

20. Valid Parentheses