数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中拼写单词的贴纸
假设我们有N种不同的贴纸。每种贴纸上都印有一个小写英文字母的单词。我们希望通过从我们的贴纸集合中剪下单个字母并重新排列它们来拼出给定的目标字符串。如果需要，我们可以多次使用每张贴纸，并且我们拥有每张贴纸无限的数量。
我们必须找到拼出目标所需的最小贴纸数量？如果任务不可能，则返回 -1。
因此，如果输入类似于 [“dog”, “sentence”, ”antenna”]，而目标是“dance”，则答案将是 3
为了解决这个问题，我们将遵循以下步骤 -
- n := 目标的大小
- N := 将n左移1位
- 定义一个大小为N的数组dp，并将其初始化为inf
- dp[0] := 0
- 用于初始化 i := 0，当 i <N 时，更新（i 增加 1），执行 -
- 如果 dp[i] 与 inf 相同，则 -
- 忽略以下部分，跳到下一次迭代
- 用于初始化 j := 0，当 j <贴纸的大小，更新（j 增加 1），执行 -
- s := stickers[j]
- x := i
- 用于初始化 k := 0，当 k <s 的大小，更新（k 增加 1），执行 -
- z := s[k]
- 用于初始化 l := 0，当 l <目标的大小，更新（l 增加 1），执行 -
- 如果 target[l] 与 z 相同，并且（将 x 右移 l 位）AND 1）与 0 相同，则 -
- x := x OR（将 1 左移 l 位）
- 退出循环
- 如果 target[l] 与 z 相同，并且（将 x 右移 l 位）AND 1）与 0 相同，则 -
- dp[x] := dp[x] 和 dp[i] + 1 的最小值
- 如果 dp[i] 与 inf 相同，则 -
- 返回 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
更新于: 2020年6月2日
335 次查看
广告