問題を解く

bfsで解くこともできるが,まず基準上dpで解く.
dp[i][j]=1番目の文字列にi個を使用し、2番目の文字列にj個を使用する場合、3番目の文字列のi+jのdp配列を使用できるか否かを格納する.
例
cat tree tcraete
で、dp[0][1]が2番目の文字列を使用する場合、2番目の文字列の1番目の要素「t」を使用して3番目の文字列の1番目に作成できるので、dp[0][1]=trueとなる.
dp[1][0]最初の文字列の最初の要素「c」を使用して、3番目の文字列の最初の(「c」!=「t」)dp[1][0]=falseを作成することはできません.
さらに進むと
dp[1][1]は、最初の文字列と2番目の文字列の両方が最初から使用されている場合に、文字列「tc」を作成できるかどうかである.
では、これは2つの場合の数に分けられます.

最初の文字列を使用しない場合、2番目の文字列のみを使用する場合は「t」を作成し、1番目の文字列を使用する場合は3番目の文字列の2番目の要素「c」を作成することができ、dp[1][1]=trueとなる.

、すなわちdp[0][1]=trueであり、最初の文字列の最初の要素は「c」であり、3番目の文字列の2番目の要素は「c」であり、「c」=「c」であるため、dp[1][1]=trueとなる.

もう一つのケースは

dp[1][1]は、第1の文字列の第1の要素を使用し、第2の文字列の1つの要素が使用されていない場合、第3の文字列の第1の要素「t」(dp[1][0]=trueの場合)を作成することができ、第2の文字列の1つの要素(「t」)を使用して第3の文字列の第2の要素「c」を作成することができる場合、dp[1][1]はtrueである.

すなわち、dp[1][0]=trueであり、2番目の文字列の1番目の要素が「t」であり、3番目の文字列の2番目の要素「c」が同じであれば、dp[1][1]=trueであるが、dp[1][0]=falseであり、「t」!=c'なので、両方の条件は成立しません.

ただし、どちらの場合も成立すれば作成できるため、最終的にdp[1][1]=trueとなる.
これらの論理に基づいてアルゴリズムを記述し,以下のコードを記述する.
✔注意事項
文字列のインデックスはゼロから始まるが,思想的および符号化的にはインデックスは1から始まる.
すなわち、1番目の文字列がa、2番目の文字列がbの場合、dp[1][1]=a[0]、b[0]の場合c[1]への文字列を作成できるかどうか.

質問リンク

boj/9177

ソースコード

PS/9177 .java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Main {
  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  static boolean [][]dp = new boolean[202][202];
  public static void main(String[] args) throws Exception {
    int n = Integer.parseInt(br.readLine());
    for(int i=0;i<n;i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      String a = st.nextToken();
      String b = st.nextToken();
      String c = st.nextToken();
      for(int j=0;j<=a.length();j++)
        Arrays.fill(dp[j], false);
      if(a.charAt(0) == c.charAt(0))
        dp[1][0] = true;
      if(b.charAt(0) == c.charAt(0))
        dp[0][1] = true;
      for(int j=0;j<=a.length();j++)
      {
        for(int k=0;k<=b.length();k++)
        {
          if (j>=1 && dp[j-1][k] && c.charAt((j+k-1)) == a.charAt(j-1))
            dp[j][k] = true;
          if(k>=1 && dp[j][k-1] && c.charAt((j+k-1)) == b.charAt(k-1))
            dp[j][k] = true;
        }
      }
      bw.write("Data set " + (i+1)+": "+(dp[a.length()][b.length()]?"yes\n":"no\n"));
    }
    bw.flush();
  }
}