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

此题重在严谨,小心每个细节处理。
字符串匹配,把点和星分情况对待。
我把问题拆分成三种情况,其中重点是第二种情况。
第二种情况又拆分成三种情况,递归去处理就好。看了大佬的解法之后,惭愧,好好学习,天天向上。


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()];
    }
};