poj 2192(検索)
4849 ワード
この問題は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;
}
}