044. Wildcard-Matching

difficulty: Hard

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

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

Method One

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for(int j = 0; j < n; j++ ) {
            if( p.charAt(j) == '*') {
                dp[0][j + 1] = true; 
            }else{
                break;
            }
        }

        for(int i = 0; i < m; i++ ) {
            for( int j = 0; j < n; j++ ) {
                char sc = s.charAt(i);
                char pc = p.charAt(j);
                if( equals(sc, pc) ) {
                    dp[i + 1][ j+ 1] = dp[i][j];
                    continue;
                }
                if( pc != '*') {
                    continue;
                }
                dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j];
            }
        }
        return dp[m][n];
    }
    public boolean equals( char s, char p) {
        return s == p || p == '?';
    }

}
​
/**
if sc === pc // === 定义是 a == b || b == ?;
如果 sc === pc 那么显然是 2d dp 各减少1
即 dp[i + 1][j + 1] = dp[ i ][ j ];
continue;
​
如果 sc !== pc;
如果 pc != * 直接说明 dp[i + 1][j + 1] = false;
​
如果 pc == *，
'*' 有两个操作，一是灭别人一位并且保留自己，
    即 dp[i + 1][j + 1] = dp[ i ][ j + 1];
    二是消灭自己，什么都不匹配，
    即 dp[i + 1][j + 1] = dp[ i + 1 ][ j ];

然后处理边界条件
空串匹配空串还是有用的 0,0 = true
p 空 s 非空都是 false;
s 空的话，p 只能是一串 ******
*/
​