10. 正则表达式匹配(动态规划)

心已赠人 2022-09-08 06:18 138阅读 0赞

[https://leetcode-cn.com/problems/regular-expression-matching/][https_leetcode-cn.com_problems_regular-expression-matching]

难度困难2320

给你一个字符串 `s` 和一个字符规律 `p`，请你来实现一个支持 `'.'` 和 `'*'` 的正则表达式匹配。

*  `'.'` 匹配任意单个字符
 *  `'*'` 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 **整个 **字符串 `s`的，而不是部分字符串。

**示例 1：**

输入：s = "aa" p = "a"
    输出：false
    解释："a" 无法匹配 "aa" 整个字符串。

**示例 2:**

输入：s = "aa" p = "a*"
    输出：true
    解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

**示例 3：**

输入：s = "ab" p = ".*"
    输出：true
    解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

**示例 4：**

输入：s = "aab" p = "c*a*b"
    输出：true
    解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

**示例 5：**

输入：s = "mississippi" p = "mis*is*p*."
    输出：false

**提示：**

*  `0 <= s.length <= 20`
 *  `0 <= p.length <= 30`
 *  `s` 可能为空，且只包含从 `a-z` 的小写字母。
 *  `p` 可能为空，且只包含从 `a-z` 的小写字母，以及字符 `.` 和 `*`。
 *  保证每次出现字符 `*` 时，前面都匹配到有效的字符

通过次数195,882提交次数619,098

class Solution {
        public boolean isMatch(String s, String p) {
            int slen = s.length();
            int plen = p.length();
            boolean [][] n = new boolean[slen+1][plen+1];
           
    
            //辅助列初始化
            n[0][0] =true;
            for(int i=1;i<plen+1;i++)
            {
                if(' '==p.charAt(i-1) ) n[0][i] = true;
                else if('*'==p.charAt(i-1))
                {
                    if(i>=2) n[0][i] = n[0][i-2];
                    else n[0][i] = true;
                } 
                else n[0][i] = false;
            }
    
            s = " "+s;
            p = " "+p;
            for(int i=1;i<slen+1;i++)
            {
                for(int j=1;j<plen+1;j++)
                {
                    // System.out.println("s[i]="+s.charAt(i)+"  "+"p[j]="+p.charAt(j));
                    if(s.charAt(i)==p.charAt(j) || p.charAt(j)=='.' )
                    {
                        n[i][j] = n[i-1][j-1];
                    } 
                    else if(p.charAt(j) =='*')
                    {
                        if(j<2 || n[i][j-2]==true) n[i][j] = true;
                        else if(((p.charAt(j-1)==s.charAt(i) || p.charAt(j-1)=='.') && n[i-1][j]==true)) n[i][j] = true;
                    }
                    else n[i][j] = false;
                }
            }
    
    
            // for(int i=0;i<slen+1;i++)
            // {
            //     for(int j=0;j<plen+1;j++)
            //     {
            //         System.out.print(n[i][j]+"  ");
            //     }
            //     System.out.println();
            // }
    
            return n[slen][plen];
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_18_color_FFFFFF_t_70_g_se_x_16][]

[https_leetcode-cn.com_problems_regular-expression-matching]: https://leetcode-cn.com/problems/regular-expression-matching/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/29b8b326555541619bfe5dd5cfb73f97.png