题目描述

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

算法1

DP $O(n^2)$

C++ 代码

    // f[i][j]: s1前i个char，和 s2前j个char 能否组成 s3前i+j个char
    // f[i][j] = ( s1[i-1]==s3[i+j-1] && f[i-1][j] ) || ( s2[j-1]==s3[i+j-1] && f[i][j-1] )
    // i=0..m, j=0..n

    // init: f[0][0] = true; s1, s2, s3 都为empty
    //      for i=1..m : f[i][0] = s1[i-1]==s3[i-1] && f[i-1][0]
    //      for j=1..n : f[0][j] = s2[j-1]==s3[j-1] && f[0][j-1]

    bool isInterleave(string s1, string s2, string s3) {
        if(s1.size() + s2.size() != s3.size()) return false;

        int m = s1.size(), n = s2.size();

        vector<vector<bool>> f(m+1, vector<bool>(n+1, false));

        f[0][0] = true;
        for(int i=1; i<=m; i++) f[i][0] = s1[i-1]==s3[i-1] && f[i-1][0];
        for(int j=1; j<=n; j++) f[0][j] = s2[j-1]==s3[j-1] && f[0][j-1];

        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                f[i][j] = ( s1[i-1]==s3[i+j-1] && f[i-1][j] ) 
                            || (s2[j-1]==s3[i+j-1] && f[i][j-1] );
            }
        }

        return f[m][n];
    }