Searching 56

QUESTION

Input a text and a wildcard pattern, implement wildcard pattern matching algorithm that finds if wildcard pattern is matched with text. The matching should cover the entire text (not partial text).\n\nThe wildcard pattern can include the characters ? and *\n? matches any single character\n* Matches any sequence of characters (including the empty sequence).

“TESTCASE_1”: “baaabab\n*****ba*****ab\n###—###SEPERATOR—###—\nYes”, “TESTCASE_2”: “baaabababaa\nbaaa?ab\n###—###SEPERATOR—###—\nNo”, “TESTCASE_3”: “baaabab\na*ab\n###—###SEPERATOR—###—\nNo”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

import java.io.*;
import java.util.*;
public class TestClass{     
     
    // Function that matches input str with
    // given wildcard pattern
    static boolean strmatch(String str, String pattern,
                                 int n, int m)
    {
        // empty pattern can only match with
        // empty string
        if (m == 0)
            return (n == 0);
     
        // lookup table for storing results of
        // subproblems
        boolean[][] lookup = new boolean[n + 1][m + 1];
     
        // initailze lookup table to false
        for(int i = 0; i < n + 1; i++)
            Arrays.fill(lookup[i], false);
        
     
        // empty pattern can match with empty string
        lookup[0][0] = true;
     
        // Only '*' can match with empty string
        for (int j = 1; j <= m; j++)
            if (pattern.charAt(j - 1) == '*')
                lookup[0][j] = lookup[0][j - 1];
     
        // fill the table in bottom-up fashion
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                // Two cases if we see a '*'
                // a) We ignore '*'' character and move
                //    to next  character in the pattern,
                //     i.e., '*' indicates an empty sequence.
                // b) '*' character matches with ith
                //     character in input
                if (pattern.charAt(j - 1) == '*')
                    lookup[i][j] = lookup[i][j - 1] ||
                                   lookup[i - 1][j];
     
                // Current characters are considered as
                // matching in two cases
                // (a) current character of pattern is '?'
                // (b) characters actually match
                else if (pattern.charAt(j - 1) == '?' ||
                    str.charAt(i - 1) == pattern.charAt(j - 1))
                    lookup[i][j] = lookup[i - 1][j - 1];
     
                // If characters don't match
                else lookup[i][j] = false;
            }
        }
     
        return lookup[n][m];
    }
     
    public static void main(String args[])
    {
      Scanner sc=new Scanner(System.in);  
      String str = "";
        String pattern = "";
      str=sc.next();
      pattern=sc.next();
        // String pattern = "ba*****ab";
        // String pattern = "ba*ab";
        // String pattern = "a*ab";
        // String pattern = "a*****ab";
        // String pattern = "*a*****ab";
        // String pattern = "ba*ab****";
        // String pattern = "****";
        // String pattern = "*";
        // String pattern = "aa?ab";
        // String pattern = "b*b";
        // String pattern = "a*a";
        // String pattern = "baaabab";
        // String pattern = "?baaabab";
        // String pattern = "*baaaba*";
     
        if (strmatch(str, pattern, str.length(),
                             pattern.length()))
            System.out.println("Yes");
        else
            System.out.println("No");
     
    }
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro