leetcode第10题,之前提交做过,今天再看到有点乱,写下来记录下;
题目:正则匹配,不过pattern串中只有小写字母,和'.'外加'*'。
其实这道题目如果没有'*'直接一路匹配过去就好了,不用想太多;但是题目中有这个,就得想办法解决了。'*'在正则中表示匹配0个或多个前一个字符,这样的话,如果当前是'*'就得知道前一个字符,这就引导我们去做从后向前的字符串匹配了,具体代码如下:

点击(此处)折叠或打开

  1. bool isMatch(string s, string p){
  2.     int s_len=s.length(), p_len=p.length();
  3.     // dp[i][j] 表示s[i:], p[j:]能否完全匹配
  4.     vector<vector<bool> > dp(s_len+1, vector<bool>(p_len+1, false));
  5.     dp[s_len][p_len]=true;// 空匹配为真
  6.     // pattern 串有可能匹配空,所以
  7.     for(int i=s_len; i>=0; i--){
  8.         for(int j=p_len-1; j>=0; j--){
  9.             // 先判断当前是否能够匹配
  10.             bool is_match = i<s_len&&(s[i]==p[j]||p[j]=='.');
  11.             if(j+1<p_len && p[j+1]=='*'){
  12.                 // 匹配0个或者多个(多个的时候用到了“后向迭代思路”)
  13.                 dp[i][j]=dp[i][j+2]||(is_match && dp[i+1][j]);
  14.             }else{
  15.                 dp[i][j]=is_match && dp[i+1][j+1];
  16.             }
  17.         }
  18.     }
  19.     return dp[0][0];
  20. }

09-02 09:30
查看更多