LeetCode(10)：正则表达式匹配

向右看齐 2021-11-06 01:08 277阅读 0赞

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

![20190809155258347.png][]

方法 1：回溯  
想法

如果没有星号（正则表达式中的 \* ），问题会很简单——我们只需要从左到右检查匹配串 s 是否能匹配模式串 p 的每一个字符。

当模式串中有星号时，我们需要检查匹配串 s 中的不同后缀，以判断它们是否能匹配模式串剩余的部分。一个直观的解法就是用回溯的方法来体现这种关系。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Njg4MTQz_size_16_color_FFFFFF_t_70][]

public boolean isMatch(String s, String p) {
          // 如果匹配的规则串为空
            if (p.isEmpty()){
                // 直接返回
                return s.isEmpty();
            }
            
            // 第一个字符的匹配结果，每次递归都需要用到
            boolean first_match = ( !s.isEmpty() && ( p.charAt(0) == s.charAt(0) || p.charAt(0) == '.' ) );
    
            // 如果匹配串的长度大于2跟第一个字符是*
            if (p.length()>=2 && p.charAt(1)=='*'){
                // *不匹配任何字符，表示0
                return (isMatch(s,p.substring(2))
                        // *匹配一个字符，递归字符串
                        || (first_match && isMatch(s.substring(1),p))
                );
            }else {
                // 如果不是*
                return first_match && isMatch(s.substring(1),p.substring(1));
            }
        }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Njg4MTQz_size_16_color_FFFFFF_t_70 1][]

[20190809155258347.png]: /images/20211104/743ddbd1fb1e40a6813da7eb3751069b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Njg4MTQz_size_16_color_FFFFFF_t_70]: /images/20211104/1a53daede2db4d8fb92c01f994d5623f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Njg4MTQz_size_16_color_FFFFFF_t_70 1]: /images/20211104/2769266900294b82aeaf7710b6850bde.png