Google CodeJAM Round 1A - Pattern Matching

help
1

I used below approach to solve this question, but got WA in 3rd Test Case.
import java.util.*;

class Solution{


public static String matchLast(String a, String b){ //b>a
    
    

    if(a.length()>b.length()){
        String temp = a;
        a = b;
        b = temp;
    }
    if(a.equals("")){
        return b;
    }
    int i = a.length()-1;
    int j = b.length()-1;

    while(i>=0 && a.charAt(i)==b.charAt(j)){
        i--;
        j--;
    }

    if(i==-1){
        return b;
    }

    return "-1";

}


public static String matchFirst(String a, String b){ //b>a
    
    //System.out.println(match)

    if(a.length()>b.length()){
        String temp = a;
        a = b;
        b = temp;
    }
    if(a.length()==0){
        return b;
    }

    int i = 0;
    int j = 0;

    while(i<a.length() && a.charAt(i)==b.charAt(j)){
        i++;
        j++;
    }

    if(i==a.length()){
        return b;
    }

    return "-1";

}

public static void main(String... args){
    
    
    Scanner in = new Scanner(System.in);
    int T = in.nextInt();
    for(int t=1;t<=T;t++){
        

        int n = in.nextInt();
        StringBuilder match = new StringBuilder("");
        
        boolean notposs = false;

        for(int i=0;i<n;i++){
            String so = in.next();
            if(notposs){
                continue;
            }
            String s="";
            for(int ii=0;ii<so.length();ii++){
                if(ii==0){
                    s+=so.charAt(ii);
                }else{
                    if(so.charAt(ii)=='*'){
                        if(s.charAt(s.length()-1)=='*'){
                            continue;
                        }
                    }
                    s+=so.charAt(ii);
                }
            }



            if(match.toString().equals("")){
                match = new StringBuilder(s);
                continue;  
            }

            int mfirst = match.indexOf("*");
            int mlast = match.lastIndexOf("*");

            int sfirst = s.indexOf("*");
            int slast = s.lastIndexOf("*");

            

                //setting first part

                String af = match.substring(0,mfirst);
                String bf = s.substring(0,sfirst);
                String matched = matchFirst(af,bf);
                //System.out.println(af);
                //System.out.println(bf);
                //System.out.println("fmatched:"+matched);
                if(matched.equals("-1")){
                    notposs=true;
                    continue;
                }
                match.replace(0,mfirst+1, matched+"*");
                //System.out.println("first:"+ match);

                //middle element
                match.replace(mfirst,mfirst+1,s.substring(sfirst,slast+1));

                //setting last part
                 mfirst = match.indexOf("*");
                 mlast = match.lastIndexOf("*");

                 sfirst = s.indexOf("*");
                 slast = s.lastIndexOf("*");
                    
                String a = match.substring(mlast+1);
                String b = s.substring(slast+1);
                matched = matchLast(a,b);
                //System.out.println(s);
                //System.out.println("a:"+a);
                //System.out.println("b:"+b);
                
                //System.out.println("secmatched:"+matched);
                if(matched.equals("-1")){
                    notposs=true;
                    continue;
                }
                match.replace(mlast+1,match.length(),matched);
               
                //System.out.println("sec:"+match);
                //System.out.println();

         

        }
        //System.out.println("MM:"+match);
        if(match.toString().contains("-1")){
            System.out.println("Case #"+t+":"+" *");
        }else{
            System.out.print("Case #"+t+":"+" ");
            for(int ii=0;ii<match.length();ii++){
                if(match.charAt(ii)!='*'){
                    System.out.print(match.charAt(ii));
                }
            }
            System.out.println();

        }
        

    }
    
}

}

What is the problem? and how can it be solved?

2

Carefully read as it is too long to describe.

Step 1:- Select the prefix of all strings just before first *
Step 2:- Select the suffix of all strings after last * an d store both these values in 2 new vectors
Step 3:- Ok and store the string leaving prefix and suffix in the main part known as stem
Cool…
Step:- 4Now one thing only you need to check is that among the selected prefixes select the
maximum length prefix and maximum length suffix answer it yourself why?
Step:- 5Then after selecting maximum length prefix then match it with all other prefixes if all prefixes are a prefix of this selected string then Ok otherwise there doesn’t exist any word satisfying above strings
Step 6:- And after maximum suffix check that all other suffixes are a part of the suffix of this string

cool…

Step 7:- And than after that for the main part(leaving prefix and suffix of any string ) append main part of all the strings after the maximum length prefix in the answer(ans string) and after appending maximum length prefix append all main parts and after that append maximum length suffix

Step 8:- And output the answer string
By substituting each * with any letter between A to Z as * can be anything so I assumed it common for all the strings

Hope it makes it clear
Submit and get the AC.

3

Yeah, I tried, missing notposs is true statement, GOT AC now, Thankyou