字符串匹配问题小结

客官°小女子只卖身不卖艺 2023-02-25 08:57 17阅读 0赞

# 字符串匹配问题小结 #

刷Leetcode时，发现有两个字符串匹配问题很巧妙，所以记录一下

## 正则表达式匹配 ##

### 问题描述 ###

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

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

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

**说明:**

*  s 可能为空，且只包含从 a-z 的小写字母。
 *  p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 \*。

**示例 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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/regular-expression-matching  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

回溯思想：

class Solution {
        
        char[] str;
        char[] pattern;
        public boolean isMatch(String s, String p) {
        
              if (s==null||p==null) {
        
                return false;
            }
            this.str = s.toCharArray();
            this.pattern = p.toCharArray();
            return matchCore(0,0);
        }
    
         /***
         * 
         * @param sStart str 开始的位置
         * @param pStart pattern 开始的位置
         * @return
         */
        boolean matchCore(int sStart,int pStart){
        
            if (sStart==str.length && pStart==pattern.length) return true;
            if (sStart!=str.length && pStart==pattern.length) return false;
    
            //说明第二个为 *
            if (pStart<pattern.length-1 && pattern[pStart+1]=='*') {
        
                if (sStart!=str.length && (pattern[pStart]==str[sStart]||pattern[pStart]=='.')) {
        
                    //相等时，需要进行判断
                    //分别为 *当作一个，当作多个，当作没有
                    return matchCore(sStart+1, pStart+2)||matchCore(sStart+1, pStart) || matchCore(sStart, pStart+2);
                    
                }else{
        
                    //不相等时，当这个*不存在
                    return   matchCore(sStart, pStart+2);
                }
            }
    
          if (sStart!=str.length && (pattern[pStart]==str[sStart]||(pattern[pStart]=='.' )))
                return matchCore(sStart+1, pStart+1);
    
            return false;
    
        }
    }

回溯比较好理解，代码也比较好实现，总结来说就：

*  当pattern\[pStart\]==str\[sStart\]||(pattern\[pStart\] ==’.’）时
    
    pattern和str都访问下一个就行
 *  pattern\[pStart+1\]==’*’（第二个字符是‘* \*’）时，分情况讨论：
    
     *  pattern\[pStart\]== str\[sStart\]||pattern\[pStart\] ==’.’),那么进行递归判断，
        
         *  sStart+1, pStart+2，‘\*‘当一个字符
         *  sStart+1, pStart，‘\*‘当多个字符
         *  sStart, pStart+2，’\*‘当多个字符

动态规划：

class Solution {
        
        public boolean isMatch(String s, String p) {
        
            int m = s.length();
            int n = p.length();
            //代表s的i和p的j的匹配
            boolean[][] f = new boolean[m + 1][n + 1];
            //表示没有字符时
            f[0][0] = true;
            for (int i = 0; i <= m; ++i) {
        
                for (int j = 1; j <= n; ++j) {
        
                    if (p.charAt(j - 1) == '*') {
        
                        f[i][j] = f[i][j - 2];
                        if (matches(s, p, i, j - 1)) {
        
                            f[i][j] = f[i][j] || f[i - 1][j];
                        }
                    }
                    else {
        
                        if (matches(s, p, i, j)) {
        
                            f[i][j] = f[i - 1][j - 1];
                        }
                    }
                }
            }
            return f[m][n];
        }
    
        public boolean matches(String s, String p, int i, int j) {
        
            if (i == 0) {
        
                return false;
            }
            if (p.charAt(j - 1) == '.') {
        
                return true;
            }
            return s.charAt(i - 1) == p.charAt(j - 1);
        }
    }

动态规划主要是要想出子问题以及动态转移方程。先给个表格，显示一下子问题的结构

转移大概这样：

![image-20200711200940453][]

状态转移方程：

*  当p\[j\]为字母和s\[i\]匹配时或者p\[j\]为’.‘，f\[i\]\[j\] = f\[i - 1\]\[j - 1\] (比较好理解)
 *  当p\[j\]为’\*‘时， f\[i\]\[j\] = f\[i\]\[j - 2\]||f\[i - 1\]\[j\]

具体可以参考：

*  https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode-solution/
 *  https://leetcode-cn.com/problems/regular-expression-matching/solution/dong-tai-gui-hua-zen-yao-cong-0kai-shi-si-kao-da-b/

## 通配符匹配 ##

### 问题描述 ###

给定一个字符串 (s) 和一个字符模式 § ，实现一个支持 ‘?’ 和 ‘\*’ 的通配符匹配。

'?' 可以匹配任何单个字符。
    '*' 可以匹配任意字符串（包括空字符串）。

两个字符串**完全匹配**才算匹配成功。

**说明:**

*  s 可能为空，且只包含从 a-z 的小写字母。
 *  p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 \*。

**示例 1:**

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

**示例 2:**

输入:
    s = "aa"
    p = "*"
    输出: true
    解释: '*' 可以匹配任意字符串。

**示例 3:**

输入:
    s = "cb"
    p = "?a"
    输出: false
    解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

**示例 4:**

输入:
    s = "adceb"
    p = "*a*b"
    输出: true
    解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

**示例 5:**

输入:
    s = "acdcb"
    p = "a*c?b"
    输出: false

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/wildcard-matching  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

回溯思想

class Solution {
        
        char[] str;
        char[] pattern;
        public boolean isMatch(String s, String p) {
        
            if (s==null||p==null) {
        
                return false;
            }
            this.str = s.toCharArray();
            this.pattern = p.toCharArray();
            return matchCore(0,0);
        }
    
         /***
         * 
         * @param sStart str开始的地方
         * @param pStart pattern 开始的位置 
         * @return
         */
        boolean matchCore(int sStart,int pStart){
        
            if (sStart==str.length && pStart==pattern.length) return true;
            if (sStart!=str.length && pStart==pattern.length) return false;
            // if(sStart>=str.length && pattern[pStart]!='*') return false;
    
            if(sStart<str.length && pattern[pStart]=='*'){
        
                //分别为 * 代表空、1个字符、多个字符
                return matchCore(sStart, pStart+1) || matchCore(sStart+1, pStart+1) || matchCore(sStart+1, pStart);
            }else if (sStart<str.length && pattern[pStart]==str[sStart]||(pattern[pStart]=='?')) {
        
                return matchCore(sStart+1, pStart+1);
            }else if (sStart==str.length && pattern[pStart]=='*') {
        
                return matchCore(sStart, pStart+1);
            }
    
            return false;
        }
    }

思路和上一题类似

动态规划:

class Solution {
        
    
        public boolean isMatch(String s, String p) {
        
     int m = s.length();
            int n = p.length();
            //dp[i][j表示 s 第i个 到p第j个是否匹配
            boolean[][] dp = new boolean[m + 1][n + 1];
            dp[0][0] = true;
            for (int i = 1; i <=n; i++) {
        
                if (p.charAt(i - 1) == '*') {
        
                    dp[0][i] = true;
                }
                else {
        
                    break;
                }
            }
    
            for (int i = 1; i <= m; ++i) {
        
                for (int j = 1; j <= n; ++j) {
        
                    if (p.charAt(j - 1) == '*') {
        
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                    } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
        
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
            return dp[m][n];
        }
    
    }

可以参照这个思路:https://leetcode-cn.com/problems/wildcard-matching/solution/yi-ge-qi-pan-kan-dong-dong-tai-gui-hua-dpsi-lu-by-/

## 总结 ##

目前就记录这两题，后续再加

[image-20200711200940453]: /images/20230209/4b2082d68cc74cfdb13100f4f610b5af.png