poj 2192(検索)

この問題は2つの文字列Aに対して、Bは規則によってCを生成することができるかどうかである.

import java.util.Scanner;



public class Main {



    public static void main(String[] args) {

        // TODO Auto-generated method stub

        Scanner scn=new Scanner(System.in);

        int len=scn.nextInt();

        for(int i=1;i<=len;i++)

        {

            

            char a[]=scn.next().toCharArray();

            char b[]=scn.next().toCharArray();

            char c[]=scn.next().toCharArray();

            

            

            if(c[c.length-1]==b[b.length-1]||c[c.length-1]==a[a.length-1])

            {

                

            

            boolean ans=dfs(a,b,c,0,0,0);

            if(ans)

            {

                System.out.println("Data set "+i+": yes");

            }

            else

            {

                System.out.println("Data set "+i+": no");

            }

            

            }

            else

            {

                    

            

                    

            

                System.out.println("Data set "+i+": no");

            }

            

            

            

        }



    }



    private static boolean dfs(char a[],char b[],char c[],int ia,int ib,int ic) {

        // TODO Auto-generated method stub

        

        if(a.length+b.length!=c.length) return false;

        if(ia<a.length&&a[ia]!=c[ic]&&ib<b.length&&b[ib]!=c[ic])  return false;

        

        if(ic==c.length)

        {

            

            

        return true;

    

        }

        

    

        if(ia<a.length&&a[ia]==c[ic])

        {

            

            if( dfs(a,b,c,ia+1,ib,ic+1)) return true;

            

            

        }

        

        if(ib<b.length&&b[ib]==c[ic])

        {

            

            if(dfs(a,b,c,ia,ib+1,ic+1)) return true;;

        }

        

        return false;

    

        

        

        

        

        

    }



}