Wild Card Pattern Matching

#1

I used DP Bottom Up

import java.util.*;

public class Main
{
public static void main(String [] args) throws Exception
{
Scanner s = new Scanner(System.in);

	String input = "";

	if(s.hasNextLine())
		input = s.nextLine();

	String str, pattern;

	if(input == "")
	{
		str = "";
		pattern = "";
	}
	else
	{
		String [] g = input.split(" ");

		str = g[0];
		
		if(g.length > 1)
			pattern = g[1];
		else
			pattern = "";
	}


	if(matching(str,pattern))
		System.out.println("1");
	else
		System.out.println("0");
}


public static boolean matching(String s, String p)
{
	int m = s.length();
	int n = p.length();

	boolean [][] strg = new boolean[m+1][n+1];

	for(int vidx1 = m; vidx1 >= 0; vidx1--)
	{
		for(int vidx2 = n; vidx2 >= 0; vidx2--)
		{
			if(vidx1 == m && vidx2 == n)
				strg[vidx1][vidx2] = true;

			else if(vidx2 == n)
				strg[vidx1][vidx2] = false;

			else if(vidx1 == m)
			{
				int i;
				for(i = vidx2; i < n; i++)
				{
					if(p.charAt(i) != '*')
						break;
				}

				if(i == n)
					strg[vidx1][vidx2] = true;
				else
					strg[vidx1][vidx2] = false;
			}

			else if(s.charAt(vidx1) == p.charAt(vidx2) || p.charAt(vidx2) == '?')
				strg[vidx1][vidx2] = strg[vidx1 + 1][vidx2 + 1];

			else if(p.charAt(vidx2) == '*')
			{
				boolean fp = strg[vidx1][vidx2 + 1];

				boolean sp = strg[vidx1 + 1][vidx2];

				strg[vidx1][vidx2] = fp || sp;
			}

			else
				strg[vidx1][vidx2] = false;
		}
	}

	return strg[0][0];
}

}

#2

this is a classic 2D DP problem, I have added that solution with comments, you can go through it and it passes all the TC as well

#3

Ok, i just changed the input taking method in my code as shown in yours and kept the rest of the logic same and now it is working for test cases

1 Like