Skip to content

44. Wildcard Matching

难度:Hard

刷题内容

原题连接

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

内容描述

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

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

˼· **- ʱ�临�Ӷ�: O(n^2)*- �ռ临�Ӷ�: O(n^2)***

�տ�ʼ����ʱ����Ϊ��һ����ģ���⣬内容描述ʱ��ŷ��ֿ�����DP����ʹ��DPʱ���ҵ�״̬ת�Ʒ��̡内容描述Ƕ�������dp[i][j]��ʾ���ַ��� p �е� i - 1����ĸ֮ǰ���ַ������ַ��� s �еĵ� j - 1����ĸ֮ǰ���Ӵ�ƥ�䣬���ǾͿ���д����Ӧ��״̬ת�Ʒ��̵�p[i] == '?'����p[i] == s[j]ʱ��dp[i + 1][j + 1] = dp[i][j],��p[i] == '*'ʱ��j < p.length(),����dp[i + 1][j + 1] = dp[i][j],����dp[i + 1][j] = dp[i][j],��󷵻�dp[p.length()][s.length() - 1]

class Solution {
public:
    bool isMatch(string s, string p) {
    if(!p.length())
        return !s.length();
    s.push_back(' ');
    int dp[p.length() + 1][s.length() + 1];
    for(int i =0;i <= p.length();++i)
        for(int j = 0;j <= s.length();++j)
            dp[i][j] = 0;

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


回到顶部