Build dp[i][j] indicating whether s[0..i-1] matches p[0..j-1].

Wildcard Matching

hard

Acceptance: 36%

Dynamic Programming

Implement a pattern matcher where '?' stands for any single character and '*' stands for any sequence of characters (including none). The entire input string must be matched by the pattern.

Examples

Example 1:

Input:s = "sequence", p = "s*nce"

Output:true

Explanation: '*' absorbs 'eque', and the remaining characters match literally.

Example 2:

Input:s = "test", p = "te?a"

Output:false

Explanation: '?' matches 's' but 'a' does not match 't'.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Wildcard Matching

Examples

Hints

Related Problems