10. Regular Expression Matching[H]正则表达式匹配

ゝ一世哀愁。 2021-11-11 13:20 287阅读 0赞

# 题目 #

--------------------

Given an input string(s) and a pattern(p), implement regular expression matching with support for '.' and '*'.  
  '.' Matches any single character.  
  '*' Matches zero or more of the preceding element.

The matching should cover the entire input string(not partial).  
**Note：**  
  s could be empty and contains only lowercase letters a-z.  
  p could be empty and contains only lowercase letters a-z, and characters . or \* .

**Example1：**  
  Input：s = "aa" p="a"  
  Output：false  
  Explanation："a" does not match the entire string "a"  
**Example2：**  
  Input：s = "aa" p="a\*"  
  Output：true  
  Explanation：".\*" means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it become "a".

**Example3：**  
  Input：s = "ab" p=".\*"  
  Output：true  
  Explanation：".*" means " zero or more (*) of any character (.) " .

# 思路 #

--------------------

### 动态规划 ###

##### Step1. 刻画一个最优解的结构特征 #####

\$dp\[i\]\[j\]\$表示\$s\[0,\\cdots,i-1\]\$与\$p\[0,\\cdots,j-1\]\$是否匹配

##### Step2. 递归定义最优解的值 #####

1.\$p\[j-1\] == s \[i-1\]\$，则状态保存，\$dp\[i\]\[j\] = dp\[i-1\]\[j-1\]\$  
2.\$p\[j-1\] ==\$ `.`，`.`与任意单个字符匹配，于是状态保存，\$dp\[i\]\[j\] = dp\[i-1\]\[j-1\]\$  
3.$p\[j-1\] == $`*`，`*`只能以`X*`的形式才能匹配，但是由于`*`究竟作为几个字符匹配不确定，此时有两种情况：

*  \$p\[j-2\] != s\[i-1\]\$，此时\$s\[0,\\cdots,i-1\]\$与\$p\[0,\\cdots,j-3\]\$匹配，即\$dp\[i\]\[j\] = dp\[i\]\[j-2\]\$
 *  \$p\[j-2\] == s\[i-1\]\$ 或者 $p\[j-2\] == $ `.`，此时应分为三种情况：  
    `*`作为零个字符，\$dp\[i\]\[j\] = dp\[i\]\[j-2\]\$  
    `*`作为一个字符，\$dp\[i\]\[j\] = dp\[i\]\[j-1\]\$  
    `*`作为多个字符，\$dp\[i\]\[j\] = dp\[i-1\]\[j\]\$

##### Step3. 计算最优解的值 #####

根据状态转移表，以及递推公式，计算dp\[i\]\[j\]

# Tips #

--------------------

### 数组初始化（python） ###

##### （1）相同的值初始化(一维数组) #####

#方法一：list1 = [a a a ]
    list1 = [ a for i in range(3)]
    #方法二:
    list1 = [a] * 3

##### （2）二维数组初始化 #####

初始化一个\$4\*3\$每项固定为0的数组

list2 = [ [0 for i in range(3)] for j in range(4)]

# C++ #

class Solution {
    public:
        bool isMatch(string s, string p) {
            int m = s.length(),n = p.length();
            bool dp[m+1][n+1];
            dp[0][0] = true;
            //初始化第0行,除了[0][0]全为false，因为空串p只能匹配空串，其他都无能匹配
            for (int i = 1; i <= m; i++)
                dp[i][0] = false;
            //初始化第0列，只有X*能匹配空串
            for (int j = 1; j <= n; j++)
                dp[0][j] = j > 1 && '*' == p[j - 1] && dp[0][j - 2];
            for (int i = 1; i <= m; i++)
            {
               for (int j = 1; j <= n; j++)
               {
                   if (p[j - 1] == '*')
                   {
                       dp[i][j] = dp[i][j - 2] || (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j];
                   }
                   else //只有当前字符完全匹配，才能传递dp[i-1][j-1] 值
                   {
                       dp[i][j] = (p[j - 1] == '.' || s[i - 1] == p[j - 1]) && dp[i - 1][j - 1];
                   }
               }
            }
            return dp[m][n];
        }
    };

# Python #

def isMatch(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: bool
            """
            len_s = len(s)
            len_p = len(p)
            dp = [[False for i in range(len_p+1)]for j in range(len_s+1)]
            dp[0][0] = True
            for i in range(1, len_p + 1):
                dp [0][i] = i>1 and dp[0][i - 2] and p[i-1] == '*'
            for i in range (1, len_s + 1 ):
                for j in range(1, len_p + 1):
                    if p[j - 1] == '*':
                        #状态保留
                        dp[i][j] = dp[i][j -2] or (s[i-1] == p[j-2] or p[j-2] == '.') and dp[i-1][j]
                    else:
                        dp[i][j] = (p[j-1] == '.' or s[i-1] == p[j-1]) and dp[i-1][j-1]
            return dp[len_s][len_p]

转载于:https://www.cnblogs.com/Jessey-Ge/p/10993447.html