codechef program #27 : Chef and the Wildcard Matching ;codechef program #28: Chef and Two Strings


TWOSTR


Problem Statement #1
Chef wants to implement wildcard pattern matching supporting only the wildcard '?'. The wildcard character '?' can be substituted by any single lower case English letter for matching. He has two strings X and Y of equal length, made up of lower case letters and the character '?'. He wants to know whether the strings X and Y can be matched or not.

Input

The first line of input contain an integer T denoting the number of test cases. Each test case consists of two lines, the first line contains the string X and the second contains the string Y.

Output

For each test case, output a single line with the word Yes if the strings can be matched, otherwise output No.

Constraints

  • 1 ≤ T ≤ 50
  • Both X and Y have equal length and the length is between 1 and 10.
  • Both X and Y consist of lower case letters and the character '?'.

Example

Input:
2
s?or?
sco??
stor?
sco??

Output:
Yes
No

Explanation

First Example: There are several ways the two strings can be matched, one of those is "score".
Second Example: There is no way to match the strings.
My Solution :
import java.util.*;
import java.lang.*;
public class Wildcard
{
static boolean blnResult;
public static String[] removeElements(String[] input, String deleteMe) {
   if (input != null) {
       List list = new ArrayList(Arrays.asList(input));
       for (int i = 0; i < list.size(); i++) {
           if (list.get(i).equals(deleteMe)) {
               list.remove(i);
           }
       }
       return list.toArray(new String[0]);
   } else {
       return new String[0];
   }
}
  
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
String Arrb[]=null;
String Arrc[]=null;
int T=in.nextInt();
for (int a=0;a
{
String b=in.next();
String c=in.next();

Arrb=b.split("");
Arrc=c.split("");

for(int j=0;j
{
if(Arrb[j].equals("?")||Arrc[j].equals("?"))
{
Arrb[j]="a";
Arrc[j]="a";
}

  
}

blnResult = Arrays.equals(Arrb,Arrc);



   if (blnResult==true)
{
System.out.println("Yes");
}
   if (blnResult==false)
   {
System.out.println("No");
   }
}

}

}






Problem Statement #2
Chef has found two very old sheets of paper, each of which originally contained a string of lowercase Latin letters. The strings on both the sheets have equal lengths. However, since the sheets are very old, some letters have become unreadable.
Chef would like to estimate the difference between these strings. Let's assume that the first string is named S1, and the second S2. The unreadable symbols are specified with the question mark symbol '?'. The difference between the strings equals to the number of positions i, such that S1i is not equal to S2i, where S1i and S2i denote the symbol at the i the position in S1 and S2, respectively.
Chef would like to know the minimal and the maximal difference between the two strings, if he changes all unreadable symbols to lowercase Latin letters. Now that you're fully aware of Chef's programming expertise, you might have guessed that he needs you help solving this problem as well. Go on, help him!

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of a test case contains a string S1.
The second line of a test case contains a string S2.
Both strings consist of lowercase Latin letters and question marks in places where the symbols are unreadable.

Output

For each test case, output the minimal and the maximal difference between two given strings separated with a single space.

Constraints

  • 1 ≤ T ≤ 100
  • 1 ≤ |S1|, |S2| ≤ 100
  • Subtask 1 (25 points): |S1| = 1
  • Subtask 2 (10 points): neither S1 nor S2 contains unreadable symbols
  • Subtask 3 (65 points): 1 ≤ |S1|, |S2| ≤ 100

Example

Input:
3
a?c
??b
???a
???a
?abac
aba?w

Output:
1 3
0 3
3 5

Explanation

Example case 1. You can change the question marks in the strings so that you obtain S1 = abc and S2 = abb. Then S1 and S2 will differ in one position. On the other hand, you can change the letters so that S1 = abc and S2 = bab. Then, the strings will differ in all three positions.
Example case 2. Change the question marks this way: S1 = dcbaS2 = dcba, then the strings will differ in 0 positions. You can also change the question marks so that S1 = aaaaS2 = dcba, then the strings will differ in 3 positions.
Example case 3. Change the question marks this way: S1 = aabacS2 = abaaw, then the strings will differ in 3 positions. Then, change the question marks this way: S1 = xabacS2 = abayw, then they will differ in 5 positions.

My Solution :
import java.util.Scanner;


public class chefandtwostrings {
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
String Arrb[]=null;
String Arrc[]=null;
int T=in.nextInt();
for (int a=0;a
{
String b=in.next();
String c=in.next();
int count=0;
int countM=0;
Arrb=b.split("");
Arrc=c.split("");
 
for (int j=0;j
{
if(Arrb[j].equals(Arrc[j])||Arrb[j].equals("?")||Arrc[j].equals("?"))
{
count++;
}
if(!Arrb[j].equals(Arrc[j])||Arrb[j].equals("?")||Arrc[j].equals("?"))
{
countM++;
}
}
System.out.println(Arrb.length-count+" "+countM);
}








}

}








  • Posted by lol ik.



    Comments

    Popular Posts