最終試験に備えて動的計画法の問題を少し練習していたところ、この問題を見つけて困惑しました。
Zippers: 3 つの文字列が与えられた場合、最初の 2 つの文字列の文字を組み合わせて 3 番目の文字列を形成できるかどうかを判断します。最初の 2 つの文字列は任意に混在させることができますが、それぞれの文字は 3 番目の文字列で元の順序のままにする必要があります。
たとえば、「cat」と「tree」から「tcarete」を形成することを検討してください。 String A: cat String B: tree String C: tcarete
ご覧のとおり、"tree" の最初の文字、"cat" の最初の 2 文字、"tree" の 2 番目と 3 番目の文字、" の最後の文字を選択することで、文字列 C を形成できます。それぞれ猫」と「木」です。
2 番目の例として、"cat" と "tree" から "catrtee" を形成することを検討してください。 String A: cat String B: tree String C: catrtee
この入力に対する答えも「はい」です
出力: A と B を組み合わせて文字列 C にできる場合は yes を出力します。A と B を組み合わせて C を形成できない場合は no を出力します。
したがって、基本的には、3 番目の文字列 C が A と B から形成できるかどうかを確認したいと考えています。CTRTEAE のようなものは No を出力します。私の最大の問題は、cat と tree の両方に文字 T が含まれていることです。そのため、ある文字が別の文字の後に来るかどうかをチェックするアルゴリズムを実行することはできません。これについて何か助けはありますか？