Regular Expression Matching

解法一：简单暴力求解

解题思路

• 对模板字符串进行处理，分为四种情况：
  1）字母*
  2）.*
  3）字母
  4）.
• 深度遍历求解

代码

class Solution {
public:
    typedef int MType;
    enum Roster{
        LetterAsterisk = 0,
        DotAsterisk,
        Letter,
        Dot
    };

    int model[101][2];

    int trans(string p) {
        int len = p.length();
        int index = 0;
        int pflag;
        for(int i = 0; i < len; i++) {
            if(p[i] == '*') continue;
            model[index][0] = int(p[i]);
            pflag = false;
            if(p[i] == '.') pflag = true;
            if(i+1 < len) {
                if(p[i+1] == '*') {
                    if(pflag) {
                        model[index][1] = DotAsterisk;
                    } else {
                        model[index][1] = LetterAsterisk;
                    }
                } else {
                    if(pflag) {
                        model[index][1] = Dot;
                    } else {
                        model[index][1] = Letter;
                    }
                }
            } else {
                if(pflag) {
                        model[index][1] = Dot;
                    } else {
                        model[index][1] = Letter;
                    }
            }
            index++;
        }
        return index;
    }

   bool dfs(int cur, string s, int pcur, int plen, int len) {
       if(cur == len) {
           for(int i = pcur; i < plen; i++) {
               if(model[i][1] == Dot || model[i][1] == Letter) return false;
           }
           return true;
       } 
       if(pcur >= plen) return false;
       switch (model[pcur][1]) {
           case LetterAsterisk:
                if(dfs(cur, s, pcur+1, plen, len) == true) return true;
                if(int(s[cur]) == model[pcur][0] && dfs(cur+1, s, pcur, plen, len) == true) return true;
                break;
           case DotAsterisk:
                if(dfs(cur, s, pcur+1, plen, len) == true) return true;  
                if(dfs(cur+1, s, pcur, plen, len) == true) return true;
                break;
           case Letter:
                if(int(s[cur]) == model[pcur][0] && dfs(cur+1, s, pcur+1, plen, len) == true) return true;  
                break;
           case Dot:
                if(dfs(cur+1, s, pcur+1, plen, len) == true) return true;
                break;

       }
       return false;
   }

    bool isMatch(string s, string p) {
        int lenOfP = trans(p);
        return dfs(0, s, 0, lenOfP, s.length());
    }
};

执行情况

此解法效率较低 执行结果

解法二：动态规划求解

解题思路

• 对模板字符串进行处理，分为四种情况：
  1）字母*
  2）.*
  3）字母
  4）.

• 动态规划求解：
  约定：input string (s) ，a pattern (p)，处理后的模式串 model (m)，字符串index(1~len)
  dp[i][j] : 表示s子串（1~i）与 m(1~j)的匹配情况
  

  递推式： 递推式

代码

class Solution {
public:
    typedef int MType;
    enum Roster{
        LetterAsterisk = 0,
        DotAsterisk,
        Letter,
        Dot
    };

    int model[101][2];

    int trans(string p) {
        int len = p.length();
        int index = 1;
        int pflag;
        for(int i = 0; i < len; i++) {
            if(p[i] == '*') continue;
            model[index][0] = int(p[i]);
            pflag = false;
            if(p[i] == '.') pflag = true;
            if(i+1 < len) {
                if(p[i+1] == '*') {
                    if(pflag) {
                        model[index][1] = DotAsterisk;
                    } else {
                        model[index][1] = LetterAsterisk;
                    }
                } else {
                    if(pflag) {
                        model[index][1] = Dot;
                    } else {
                        model[index][1] = Letter;
                    }
                }
            } else {
                if(pflag) {
                        model[index][1] = Dot;
                    } else {
                        model[index][1] = Letter;
                    }
            }
            index++;
        }
        return index-1;
    }

    bool isMatch(string s, string p) {
        int mlen = trans(p);
        int slen = s.length(); 
        bool dp[slen+1][mlen+1];

        for(int i = 0; i <= slen; i++) dp[i][0] = false;
        dp[0][0] = true;

        for(int i = 0; i <= slen; i++)
          for(int j = 1; j <= mlen; j++)
          {     
                dp[i][j] = false;  
                if(i > 0 && dp[i-1][j]) {
                    if((model[j][1] == LetterAsterisk && model[j][0] == int(s[i-1])) || model[j][1] == DotAsterisk) {
                        dp[i][j] = true;
                        continue;
                    }
                } 
                if(dp[i][j-1]) {
                    if((model[j][1] == LetterAsterisk) || model[j][1] == DotAsterisk) {
                        dp[i][j] = true;
                        continue;
                    }
                } 
                if(i > 0 && j > 0 && dp[i-1][j-1]) {
                    switch(model[j][1]){
                    case LetterAsterisk:
                    case Letter:
                        if(model[j][0] == int(s[i-1])) dp[i][j] = true;
                        break;
                    case DotAsterisk:
                    case Dot:
                        dp[i][j] = true;
                        break;
                }
             }
              
          }
          return dp[slen][mlen];
    }
};

执行情况

执行情况