2014-05-12 06:42

原题：

Write your own regular expression parser for following condition: az*b can match any string that starts with and ends with b and 0 or more Z's between. for e.g. azb, azzzb etc. a.b can match anything between a and b e.g. ajsdskjb etc. Your function will have to parameters: Input String and Regex. Return true/false if the input string satisfies the regex condition. Note: The input string can contain multiple regex. For e.g. az*bc.g

题目：实现正则表达式中的“*”和“.”功能，不过题目中给定的“.”实际上是“.*”。

解法：Leetcode上有这题，所以我估计是这题的出题者自己记错了，所以说错了“.”的意义。我的Leetcode题解在此：。

代码：

1 // http://www.careercup.com/question?id=4639756264669184 2 #include 
     
       3 #include 
      
        4 using namespace std; 5  6 class Solution { 7 public: 8     bool isMatch(const char *s, const char *p) { 9         int i, j;10         int ls, lp;11         vector
       
         last_i_arr;12         vector
        
          last_j_arr;13         14         if (s == nullptr || p == nullptr) {15             return false;16         }17         18         ls = strlen(s);19         lp = strlen(p);20         if (lp == 0) {21             // empty patterns are regarded as match.22             return ls == 0;23         }24         25         // validate the pattern string.26         for (j = 0; j < lp; ++j) {27             if (p[j] == '*' && (j == 0 || p[j - 1] == '*')) {28                 // invalid pattern string, can't match.29                 return false;30             }31         }32         33         int last_i, last_j;34         35         i = j = 0;36         last_i = -1;37         last_j = -1;38         while (i < ls) {39             if (j + 1 < lp && p[j + 1] == '*') {40                 last_i_arr.push_back(i);41                 last_j_arr.push_back(j);42                 ++last_i;43                 ++last_j;44                 j += 2;45             } else if (p[j] == '.' || s[i] == p[j]) {46                 ++i;47                 ++j;48             } else if (last_j != -1) {49                 if (p[last_j_arr[last_j]] == '.' || s[last_i_arr[last_i]] == p[last_j_arr[last_j]]) {50                     // current backtracking position is still available.51                     i = (++last_i_arr[last_i]);52                     j = last_j_arr[last_j] + 2;53                 } else if (last_j > 0) {54                     while (last_j  >= 0) {55                         // backtrack to the last backtracking point.56                         --last_i;57                         --last_j;58                         last_i_arr.pop_back();59                         last_j_arr.pop_back();60                         if (last_j >= 0 && (p[last_j_arr[last_j]] == '.' || s[last_i_arr[last_i]] == p[last_j_arr[last_j]])) {61                             i = (++last_i_arr[last_i]);62                             j = last_j_arr[last_j] + 2;63                             break;64                         }65                     }66                     if (last_j == -1) {67                         return false;68                     }69                 } else {70                     // no more backtracking is possible.71                     return false;72                 }73             } else {74                 return false;75             }76         }77         78         while (j < lp) {79             if (j + 1 < lp && p[j + 1] == '*') {80                 j += 2;81             } else {82                 break;83             }84         }85         86         last_i_arr.clear();87         last_j_arr.clear();88         return j == lp;89     }90 };