题解 | #正则表达式匹配#

正则表达式匹配

http://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4

不信邪，硬是把它搞出来了。写了好几遍，调试了好几次。总是有点细节问题，遗漏几个用例。

此题重在严谨，小心每个细节处理。

字符串匹配，把点和星分情况对待。

我把问题拆分成三种情况，其中重点是第二种情况。

第二种情况又拆分成三种情况，递归去处理就好。看了大佬的解法之后，惭愧，好好学习，天天向上。

bool match(string str, string pattern) {
        // write code here
        if(str.size() == 0 && pattern.size() == 0){
//             cout << "1 str: " << str << ", pattern: " << pattern << endl;
            return true;
        }
        
        if(pattern.size() > 0){
           if(pattern.size() == 1){
//                cout << "2 str: " << str << ", pattern: " << pattern << endl;
               return pattern == str || (str.size()==1 && pattern[0] == '.');
           }     
       
           if(pattern[1] != '*'){
               if(str.size() == 0 || (str[0] != pattern[0] && pattern[0] != '.')){
//                    cout << "3 str: " << str << ", pattern: " << pattern << endl;
                   return false;
               }
               
               return match(str.substr(1), pattern.substr(1));
           }else{
               bool flag = false;
               while(str.size() > 0){
                   if(flag || (str[0] != pattern[0] && pattern[0] != '.')){
                       break;
                   }
                   
                   if(pattern.size() > 2){
                      flag |= match(str, pattern.substr(2));    
                   }else{
                       flag |= match(str, "");
                   }
                   str = str.substr(1);
               }
               
//                cout << "4 str: " << str << ", pattern: " << pattern << endl;
               return flag || match(str, pattern.substr(2));
           }
        }else{
            
//             cout << "5 str: " << str << ", pattern: " << pattern << endl;
            return false;
        }
    }

大佬的动态规划确实巧妙很多，判断的状态也少很多。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        if(!pattern.size()){
            return !str.size();
        }
        
        bool dp[str.size()+1][pattern.size()+1];
        memset(dp, 0, (str.size()+1) * (pattern.size()+1) * sizeof(bool));
        dp[0][0] = true;
        
        for(int i=0;i<=str.size();i++){
            for(int j=0;j<=pattern.size();j++){
                if(j>1 && pattern[j-1] == '*'){
                    dp[i][j] |= dp[i][j-2];
                    if(i>0 && (str[i-1] == pattern[j-2] || pattern[j-2] == '.')){
                        dp[i][j] |= dp[i-1][j];
                    }
                }else{
                    if(i>0 && j>0 && (str[i-1] == pattern[j-1] || pattern[j-1] == '.')){
                        dp[i][j] = dp[i-1][j-1];
                    }   
                }
            }
        }
        
        return dp[str.size()][pattern.size()];
    }
};