Wednesday, February 25, 2015

LeetCode [10] Regular Expression Matching

10. Regular Expression Matching
Hard
Given an input string (s) and a pattern (p), 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).
Note:
  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
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:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
  • i is the index of the first string and i=1 now
  • j is the index of the first string and j=1 now
  • '*' matches zero 'b'.  Call isMatch(s, p, i, j+2, ns, np) at line 11
    • ac
    • ab*c
  • '*' matches 1 'b'. Call isMatch(s, p, ++i, j+2, ns, np) at line 13. ++i=2.
    • abc
    • ab*c
  • '*' matches 2 'b'.  Call isMatch(s, p, ++i, j+2, ns, np) at line 13. ++i=3. 
    • abbc
    • ab*c
  • '*' matches 3 'b'.  Call isMatch(s, p, ++i, j+2, ns, np) at line 13. ++i=4.
    • abbbc
    • ab*c
  • ... ...
  • (j<np-1&&p[j+1]=='*') in line 9 handles cases like 
    • ""
    • "*c*c"

 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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//C: method1 38ms
class Solution {
public:
    bool match1Char(const char *s, const char *p){
        return *s==*p||(*p=='.'&&*s!='\0');
    }
    
    bool isMatch(const char *s, const char *p) {
        if(*p=='\0') return *s=='\0';
        if(*(p+1)!='*'){
            if(!match1Char(s, p)) return false;
            return isMatch(s+1, p+1);
        }else{
            if(isMatch(s, p+2)) return true;
            while(match1Char(s, p)){
                if(isMatch(++s, p+2)) return true;
            }
        }
        return false;
    }
};

//C: method1 38ms
class Solution {
public:
    bool match1Char(const char *s, const char *p){
        return *s==*p||(*p=='.'&&*s!='\0');
    }
    
    bool isMatch(const char *s, const char *p) {
        if(*p=='\0') return *s=='\0';
        if(*(p+1)!='*'){
            if(!match1Char(s, p)) return false;
            return isMatch(s+1, p+1);
        }else{
            if(isMatch(s, p+2)) return true;
            while(match1Char(s, p)){
                if(isMatch(++s, p+2)) return true;
            }
        }
        return false;
    }
};

//C++: method1 28ms
bool isMatch(char* s, char* p) {
    if(*s){
        if((*s==*p || *p=='.') && isMatch(s+1, p+1)){
            return true;
        }else if(*(p+1)=='*'){
            if(isMatch(s, p+2)) return true;
            while(*s){
                if((*s==*p || *p=='.')){
                    if(isMatch(s+1, p+2)) return true;
                    s++;
                }else{
                    return false;
                }
            }
        }
        return false;
    }
    while(*p && *(p+1)=='*') p += 2;
    while(*p=='*') p++;
    return *p=='\0';
}

//C++: method1 428ms
class Solution {
public:
    bool isMatch(string s, string p) {
        return isMatch(s, p, 0, 0, (int)s.size(), (int)p.size());
    }
    bool isMatch(string s, string p, int s_start, int p_start, int ns, int np){
        int i = s_start, j = p_start;
        while((i<ns||(j<np-1&&p[j+1]=='*')) && j<np){
            if(j<np-1&&p[j+1]=='*'){
                if(isMatch(s, p, i, j+2, ns, np)) return true;
                while(i<ns && (s[i]==p[j]||p[j]=='.')){
                    if(isMatch(s, p, ++i, j+2, ns, np)) return true;
                }
                return false;
            }else{
                if(s[i]==p[j]||p[j]=='.'){ i++; j++;}
                else return false;
            }
        }
        return (i==ns && j==np);
    }
};


 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
class Solution {
    public boolean isMatch(String s, String p) {
        int ns = s.length(), np = p.length(), i = 0, j = 0;
        while(i<ns && j<np){
            if(j<np-1 && p.charAt(j+1)=='*'){
                if(isMatch(s.substring(i), p.substring(j+2))) return true;
                while(i<ns && (p.charAt(j)=='.' || s.charAt(i)==p.charAt(j))){
                    if(isMatch(s.substring(i+1), p.substring(j+2))) return true;
                    i++;
                }
                return false;
            }else{
                if(p.charAt(j)=='.' || s.charAt(i)==p.charAt(j)){
                    i++;
                    j++;
                }else{
                    return false;
                }
            }
        }

        //j==np
        if(i<ns) return false;
        //i==ns
        if(j<np){
            if(j<np-1 && p.charAt(j+1)=='*') return isMatch("", p.substring(j+2));
            else return false;
        }
        
        return true;
    }
}
Posted by at
Labels: , , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)