LeetCode 44.Wildcard Matching题目解析-wowAC

Description

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).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

题目复述

实现字符串匹配,需要支持'?'和'*'。

'?':匹配任意单个字符

'*':匹配任何字符序列(包括空字符序列)

题目解析

1.动态规划方法

    看到这个题目最容易想到的方法是回溯法,然而这道题使用回溯法会超时,我们考虑动态规划的方法。

    定义: dp[i][j]表示s[i – s.length()-1]和p[j – p.length()-1]是否匹配。

    考虑边界条件:

        dp[s.length()][p.length()] = 1

        dp[0 – s.length()-1][p.length()] = 0

        dp[s.length()][0 – p.length()]可能为0可能为1(["", "***"]或者["a", "a***"])

    状态转移方程: dp[i][j] = 1当且仅当

         (1)p[j]='*'且dp[k][j+1] = 1, i<=k<=s.length() *匹配任意序列

         (2)p[j]='?'且dp[i+1][j+1] = 1   ?匹配一个字符

         (3)p[j]==s[i]且dp[i+1][j+1] = 1 两个位置字符相等情

class Solution {
public:
    
    bool isMatch(string s, string p) {
        bool dp[1500][1500];
        memset(dp, 0, sizeof(dp));
        
        
        dp[s.length()][p.length()] = 1;
        for(int j=p.length()-1; j>=0; j--)
            for(int i=s.length(); i>=0; i--) {
                if(p[j] == '*') {
                    for(int k=i; k<=s.length(); k++)
                        if(dp[k][j+1] == 1) {
                            dp[i][j] = 1;
                            break;
                        }
                }else if(p[j] == '?') {
                    dp[i][j] = dp[i+1][j+1];
                }else {
                    if(i<s.length() && j<p.length() && s[i] == p[j]) 
                        dp[i][j] = dp[i+1][j+1];
                }
            }
        return dp[0][0];
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注