Redirecting to
NADOS


  Prev   Next

WILDCARD PATTERN MATCHING







A ship is safe in harbor, but that's not what ships are for.

WILDCARD PATTERN MATCHING

Hey coder. Let's start with a new question, "Wildcard Pattern Matching".

We want you to go through the problem first to understand its outline.


Important Links : Problem Link, Solution Video


  • You are given two strings s1 and s2 where s1 represents a text and s2 represents a wildcard pattern.
  • You have to print 'true' if the wildcard pattern is matched with the given text, otherwise print 'false'.
  • The wildcard pattern can include the characters '?' and '*'
    '?' - matches any single character
    '*' - matches any sequence of characters (including the empty sequence).

Let s1= "baaabab" and s2= "ba*a?".

img

We let the value of '*' be "aab" and value of '?' be 'b'. According to our assignment, the text and the string match each other.

WHAT
  • We make a 2D array for dynamic programming of dimensions (s2.length()+1) *(s1.length()+1) as shown in figure 2.
    img
  • In figure 3, the marked cell stores if the strings "aabab" and "a*a?" match each other or not.
    img
  • We start solving this dp array for the bottom right most corner cell. We know that the blank character in s1 matches the blank character of s2.
    Also, since a blank pattern cannot match a filled string, therefore the rest of the last row stores false.
    img
  • Next, we need to check if the blank of the text string matches the '*' of the pattern string. If '*' is a blank then we match "a?" with the blank. Therefore this cell takes on the value of the cell below it, i.e. false.
    img
  • Reader, you know that we can come across either '?' or '*' or a character. Let's discuss what to do for each of them.
  • For '?':
    img
    If the dp array is like figure 6, then for cell marked 1, we need to match the red highlighted strings of s1 and s2.
    Since, '?' can match any single character, so we assume it matches the character 'a' of the text string.
    Now, we are left to match the rest of the string "a?" and "bab".
    The answer to this smaller problem is stored in the cell marked 2 which lies diagonal to it.
  • For a character :
    For this we have 2 cases.
    1. The characters match.
      img
      In figure 7, just like in '?', for cell 1, we first match the first character of the string. Here it is the same for both the strings i.e. 'a'. So we try to match the strings "a?" and "bab" whose value is stored in cell 2.
    2. The characters don't match.
      img
      Here since the characters are clearly not equal, therefore we simply store false in the marked cell.
  • For '*'.
    img

For cell 1, figure 9 shows 5 cases.

  1. If '*' matches a blank, then we need to compare "a?" with "abab". So in cell 1 we store the answer of cell 2.
  2. If '*' matches character 'a' of the text string, then we need to compare "a?" with "bab". So in cell 1 we store the answer of cell 3.
  3. If '*' matches "ab" of the text string, then we need to compare "a?" with "ab". So in cell 1 we store the answer of cell 4.
  4. If '*' matches "aba" of the text string, then we need to compare "a?" with "b". So in cell 1 we store the answer of cell 5.
  5. If '*' matches "abab", then we need to compare "a?" with a blank. So in cell 1 we store the answer of cell 6.
  • Using the above rules, we fill the rest of the cells. We suggest you attempt it yourself first and watch the solution video "Wildcard Pattern Matching" for an in depth understanding.
HOW

Reader, we assure you if you have properly understood the "WHAT" part of this question, you will have no problem in coding it as it is pretty straightforward.

In case you get stuck we want you to refer to the code given below.

import java.io.*; import java.util.*; public class Main { public static boolean solution(String str, String pattern) { boolean[][]dp=new boolean[pattern.length()+1][str.length()+1]; for(int i=dp.length-1;i>=0;i--){ for(int j=dp[0].length-1;j>=0;j--){ if(i==dp.length-1 && j==dp[0].length-1){ dp[i][j]=true; }else if(i==dp.length-1){ dp[i][j]=false; }else if(j==dp[0].length-1){ if(pattern.charAt(i)=='*'){ dp[i][j]=dp[i+1][j]; } else{ dp[i][j]=false; } }else{ if(pattern.charAt(i)=='?'){ dp[i][j]=dp[i+1][j+1]; }else if(pattern.charAt(i)=='*'){ dp[i][j]=dp[i+1][j]|| dp[i][j+1]; }else if(pattern.charAt(i)==str.charAt(j)){ dp[i][j]=dp[i+1][j+1]; } else{ dp[i][j]=false; } } } } return dp[0][0]; } public static void main(String[] args) { Scanner scn = new Scanner(System.in); String s1 = scn.next(); String s2 = scn.next(); System.out.println(solution(s1,s2)); } }
java; true";
Analysis
Time Complexity:

O(n2)

Space Complexity:

O(n2)

We have come to the end of our discussion. We hope to see you in the next question.

If you have any doubts about this problem, we suggest you watch its solution video.

Goodbye.

Wildcard Pattern Matching
Dynamic Programming and Greedy
Author: Shreeya Gupta
 
Run
Id Name