在C ++中拼写单词的贴纸

假设我们有N种不同类型的贴纸。在每种类型的贴纸上都有一个小写的英语单词。我们希望通过从贴纸集合中切出单个字母并重新排列来拼出给定的目标字符串。如果需要，我们可以多次使用每个标签，并且每个标签都有无限量。

我们必须找到拼写目标所需的最少数量的贴纸？如果无法完成任务，则返回-1。

因此，如果输入的内容类似于[“ dog”，“ sentence”，“ antenna”]，而目标是“ dance”，则答案将为3

为了解决这个问题，我们将遵循以下步骤-

• n：=目标大小

• N：=向左移1次n次

• 定义大小为N的数组dp，并使用inf对其进行初始化

• dp [0]：= 0

• 对于初始化i：= 0，当i <N时，更新（将i增加1），执行-

• s：=贴纸[j]

• x：=我

• 对于初始化k：= 0，当k <s的大小时，更新（将k增加1），执行-

• dp [x]：= dp [x]和dp [i]的最小值+ 1

• 如果target [l]与z相同，并且（右移x，l位）AND 1）等于0，则-

• x：= x OR（将1向左移l位）

• 从循环中出来

• z：= s [k]

• 对于初始化l：= 0，当l <目标大小时，更新（将l增加1），执行-

• 忽略以下部分，跳至下一个迭代

• 如果dp [i]与inf相同，则-

• 对于初始化j：= 0，当j <贴纸大小时，更新（将j增加1），-

• return dp [N-1]是inf然后用-1设置，否则用dp [N-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