• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.



Problem Statement:


Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).


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

Solution:


If you have already read the chapter Regular Expression Matching, which I highly recommend that you do, I would suggest you to first try to solve this problem yourself and write down the recurrence relation, and then come back and peruse this chapter, as this would be a good problem solving practice for you and would boost your confidence, especially if you are preparing for a test or interview.

Java Code:


Let's look at the well-commented code below. The comments in the code describe the algorithm and implementation logic in details:



This is a Premium content.
Please subscribe to Algorithms course to access the code.




Python Code:


Let's look at the well-commented code below. The comments in the code describe the algorithm and implementation logic in details:



This is a Premium content.
Please subscribe to Algorithms course to access the code.





The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave