C++で単語を綴るステッカー

N種類のステッカーがあるとします。各タイプのステッカーには、小文字の英語の単語が付いています。ステッカーのコレクションから個々の文字を切り取り、それらを再配置することによって、指定されたターゲット文字列を綴りたいと思います。必要に応じて各ステッカーを複数回使用でき、各ステッカーの数量は無限です。

ターゲットを綴るのに必要なステッカーの最小数を見つける必要がありますか？タスクが不可能な場合は、-1を返します。

したがって、入力が["dog"、 "sentence"、 "antenna"]のようで、ターゲットが "dance"の場合、答えは3になります

これを解決するには、次の手順に従います-

• n：=ターゲットのサイズ
• N：=1を左にn回シフト
• サイズNの配列dpを定義し、infで初期化します
• dp [0]：=0
• iを初期化する場合：=0、i
• dp [i]がinfと同じ場合、-
  • 次の部分を無視し、次の反復にスキップします
• jを初期化する場合：=0、j <ステッカーのサイズの場合、更新（jを1増やします）、実行-
  • s：=ステッカー[j]
  • x：=i
  • kを初期化する場合：=0、k
  • z：=s [k]
  • 初期化l：=0の場合、l <ターゲットのサイズの場合、更新（lを1増やします）、実行-
    • target [l]がzと同じで、（右シフトx、lビット）AND 1）が0と同じ場合、-
      • x：=x OR（1を左にlビットシフト）
      • ループから抜け出す
• dp [x]：=最小のdp[x]およびdp[i] + 1

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minStickers(vector<string>& stickers, string target) {
      int n = target.size();
      int N = 1 << n;
      vector <int> dp(N, INT_MAX);
      dp[0] = 0;
      for(int i = 0; i < N; i++){
         if(dp[i] == INT_MAX) continue;
         for(int j = 0; j < stickers.size(); j++){
            string s = stickers[j];
            int x = i;
            for(int k = 0; k < s.size(); k++){
               char z = s[k];
               for(int l = 0; l < target.size(); l++){
                  if(target[l] == z && ((x >> l) & 1) == 0){
                     x |= (1 << l);
                     break;
                  }
               }
            }
            dp[x] = min(dp[x], dp[i] + 1);
         }
      }
      return dp[N - 1] == INT_MAX? -1 : dp[N - 1];
   }
};
main(){
   Solution ob;
   vector<string> v = {"dog", "sentence","antenna"};
   cout << (ob.minStickers(v, "dance"));
}

入力

["dog", "sentence","antenna"]
"dance"

出力

3