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

class Solution {
public:
    /*
        把能确定的都确定下来,(能确定的一般都是只能满足一种迭代方程的,或者不再迭代方程定义域内的)
    */
    bool match(string str, string pat) {
        return cat(str,pat,0,0);
    }
    
    bool cat(string str,string pat,int i,int j){
      if(j == pat.size()) return i == str.size();
      bool first_match = i < str.size() && (pat[j] == '.' || pat[j] == str[i]); // 当前字符是否匹配!
      if(j + 1 < pat.size() && pat[j+1] == '*'){// 如果下一步遇到*
          return cat(str,pat,i,j+2) || (first_match && cat(str,pat,i+1,j));// 考虑*代表0个 或多个!
      }else {
          return first_match && cat(str,pat,i+1,j+1);// 没遇到*同时先后移动!
      }
    }
};