Regular Expression Matching

hard

Acceptance: 36%

Dynamic Programming

Implement a pattern matcher that supports two special characters: '.' which matches any single character, and '*' which matches zero or more repetitions of the character immediately before it. The match must account for the entire input string, not just a substring.

Examples

Example 1:

Input:s = "abbc", p = "a.*c"

Output:true

Explanation: '.' followed by '*' matches any number of any character, covering 'bb'. Then 'c' matches 'c'.

Example 2:

Input:s = "hello", p = "he*lo"

Output:false

Explanation: 'e*' can match zero or more 'e's, giving 'hlo' or 'helo' or 'heelo' etc., but none equals 'hello'.

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
    }
}

Regular Expression Matching

Examples

Hints

Related Problems