Match String with Wildcard Pattern
This program checks if a string matches a wildcard pattern.
Problem Statement
Write a Java program to check if "abcdef" matches pattern "adf".
Source Code
| 1 | public class WildcardMatching { |
| 2 | public static boolean isMatch(String str,String pat){ |
| 3 | int m=str.length(), n=pat.length(); |
| 4 | boolean[][] dp=new boolean[m+1][n+1]; |
| 5 | dp[0][0]=true; |
| 6 | for(int j=1;j<=n;j++){ |
| 7 | if(pat.charAt(j-1)=='*') dp[0][j]=dp[0][j-1]; |
| 8 | } |
| 9 | for(int i=1;i<=m;i++){ |
| 10 | for(int j=1;j<=n;j++){ |
| 11 | if(pat.charAt(j-1)=='*') |
| 12 | dp[i][j]=dp[i][j-1]||dp[i-1][j]; |
| 13 | else if(pat.charAt(j-1)=='?'||pat.charAt(j-1)==str.charAt(i-1)) |
| 14 | dp[i][j]=dp[i-1][j-1]; |
| 15 | } |
| 16 | } |
| 17 | return dp[m][n]; |
| 18 | } |
| 19 | public static void main(String[] args) { |
| 20 | System.out.println("Eduinq Wildcard Matching"); |
| 21 | System.out.println("Match result: "+isMatch("abcdef","a*d*f")); |
| 22 | } |
| 23 | } |
Program Output
Eduinq Wildcard Matching Match result: true
Explanation
A DP table tracks whether prefixes of the string match prefixes of the pattern, with '*' allowed to match any sequence (including empty) and '?' matching any single character, together determining whether the whole string matches the wildcard pattern.