leetcode.44.通配符匹配问题-动态规划的两种写法

秒速五厘米 2022-10-25 12:59 138阅读 0赞

## 题目描述 ##

https://leetcode-cn.com/problems/wildcard-matching/

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

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

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

### dp写法一 ###

class Solution {
    
        public boolean isMatch(String str, String pattern) {
            //定义states状态数组，对于i、j为states数组的下标,代表str的中第i个字符前的字符是否匹配pattern中的第j个字符前的字符
            boolean[][] states = new boolean[str.length() + 1][pattern.length() + 1];
            //如果str和pattern都是空串，则都是匹配的;默认状态全为false,只需要对0,0坐标定为true
            states[0][0] = true;
            //匹配pattern的前面的*号
            for (int j = 1; j < pattern.length() + 1; j++) {
                if (pattern.charAt(j - 1) == '*') {
                    states[0][j] = true;
                } else {
                    break;
                }
            }
    
            for (int i = 1; i < str.length() + 1; i++) {
                char s = str.charAt(i - 1);
                for (int j = 1; j < pattern.length() + 1; j++) {
                    char p = pattern.charAt(j - 1);
                    if (s == p || p == '?') {
                        //当前字段匹配，上一个字段匹配则这个也匹配
                        states[i][j] = states[i - 1][j - 1];
                    } else if (p == '*') {
                        //当前位是通配符,上一个字段匹配了就行，比?范围更宽泛
                        states[i][j] = states[i][j - 1] || states[i - 1][j] ||states[i-1][j - 1];
                    }
                }
            }
            //返回str的所有长度是否匹配pattern的所有长度
            return states[str.length()][pattern.length()];
        }
    }

### dp写法二 ###

https://introcs.cs.princeton.edu/java/51language/Wildcard.java

public class Solution {
    
        public boolean isMatch(String text, String pattern) {
            // add sentinel so don't need to worry about *'s at end of pattern
            text += '\0';
            pattern += '\0';
    
            int n = pattern.length();
    
            //定义状态数组,坐标序号代表到第n个是否匹配
            boolean[] states = new boolean[n + 1];
            boolean[] old = new boolean[n + 1];
            old[0] = true;
    
            for (int i = 0; i < text.length(); i++) {
                char c = text.charAt(i);
                states = new boolean[n + 1]; // initialized to false
                for (int j = 0; j < n; j++) {
                    char p = pattern.charAt(j);
    
                    // hack to handle *'s that match 0 characters
                    if (old[j] && (p == '*'))
                        //上一位是匹配的,且这一位是通配符
                        old[j + 1] = true;
    
                    if (old[j] && (p == c))
                        //上一位是匹配的,当前位字符串匹配,则当前位为true
                        states[j + 1] = true;
                    if (old[j] && (p == '?'))
                        //同上
                        states[j + 1] = true;
                    if (old[j] && (p == '*'))
                        //上一位必须也是true
                        states[j] = true;
                    if (old[j] && (p == '*'))
                        //当前位为true
                        states[j + 1] = true;
                }
                old = states;
            }
            return states[n];
        }
    }