0044. Wildcard Matching (H)

佚名 4年前 (2020-06-29) 算法 679人围观抢沙发百度已收录

Wildcard Matching (H)

题目

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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 like ? or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

题意

实现一个包含'?'、'*'的正则匹配。其中，'?'可以匹配任意一个字符，'*'可以匹配任意长度的任意字符。

思路

问题与解法都与 0010. Regular Expression Matching (H) 相似，同样可以使用记忆化搜索和动态规划来解决 (该题直接递归不做优化会超时)。

代码实现

Java

记忆化搜索

class Solution {
    public boolean isMatch(String s, String p) {
        return isMatch(s, 0, p, 0, new int[s.length() + 1][p.length() + 1]);
    }

    private boolean isMatch(String s, int sHead, String p, int pHead, int[][] record) {
        if (pHead == p.length()) {
            return sHead == s.length();
        }

        if (record[sHead][pHead] != 0) {
            return record[sHead][pHead] == 1 ? true : false;
        }

        boolean match = false;
        if (p.charAt(pHead) == '*') {
            match = sHead < s.length() && isMatch(s, sHead + 1, p, pHead, record) 
              			|| isMatch(s, sHead, p, pHead + 1, record);
        } else {
            match = sHead < s.length() && (s.charAt(sHead) == p.charAt(pHead) || p.charAt(pHead) == '?') 
              			&& isMatch(s, sHead + 1, p, pHead + 1, record);
        }

        record[sHead][pHead] = match ? 1 : -1;
        return match;
    }
}

动态规划

class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;

        for (int i = 0; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || i > 0 && dp[i - 1][j];
                } else {
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?');
                }
            }
        }

        return dp[s.length()][p.length()];
    }
}