Loading...
Loading...
Loading...
Nikhil is writing a search box for his college library app. A search pattern uses lowercase letters and two special characters: - . matches any one letter. - * means the character just before it may appear any number of times, including zero. So a* matches the empty text, a, aa and so on, and .* matches any text.
The pattern must match the whole text, not just a part of it. Print YES if it does, otherwise NO.
YES if p matches all of s, otherwise NO.. and *.* comes right after a letter or a ..Example 1
Input
aab c*a*b
Output
YES
c* is used zero times, a* covers aa, and b matches b.
Example 2
Input
mississippi mis*is*p*.
Output
NO
After mis*is* covers mississ, the text still has ippi, but p*. can only cover some p's and then one letter.
Try the problem first. Open one hint at a time.
Compare the text and the pattern from the left. A plain letter or . uses up one character of each.
A letter followed by * gives two choices: skip the pair, or use it for one character of the text and stay on the same pair. Trying every choice again and again repeats a lot of work.
The answer depends only on how much of the text and how much of the pattern are left. Save the answer for every pair (i, j).
Use dynamic programming: dp[i][j] is true when the first i characters of s match the first j characters of p.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor