我要评论3213. 最小代价构造字符串
题目描述：
给你一个目标字符串 target，一个字符串数组 words，以及一个对应的花费数组costs，每个word对应一个cost
你可以从words数组中选择任意数量的任意字符串，拼接起来，求拼接成target的最小花费
如果不能拼成target则输出-1
1 <= target.length <= 5 * 1041 <= words.length == costs.length <= 5 * 1041 <= words[i].length <= target.length- 所有
words[i].length的总和小于或等于5 * 104 target和words[i]仅由小写英文字母组成。1 <= costs[i] <= 104
思路
考虑动态规划，设状态 d p [ i ] dp[i] dp[i]表示构造出 t a r g e t target target前 i i i位的最小花费
状态转移方程：
- 假设 w o r d s [ j ] words[j] words[j]能匹配 t a r g e t [ i ] target[i] target[i]到 t a r g e t [ i + l e n j − 1 ] target[i+len_j-1] target[i+lenj−1]，
- 则状态转移方程为 d p [ i + l e n j + 1 ] = m i n ( d p [ i + l e n j + 1 ] , d p [ i ] + c o s t j ) dp[i+len_j+1] = min(dp[i+len_j+1], dp[i] + cost_j) dp[i+lenj+1]=min(dp[i+lenj+1],dp[i]+ costj)
所以我们需要想个对每个 w o r d word word求出在 t a r g e t target target中所有匹配成功的位置，方便进行状态转移
正解是用后缀数组或者ac自动机来求，不过我不会，我用的字典树进行代替一下，解决匹配问题
但是，字典树最坏的情况会是 o ( n 2 ) o(n^2) o(n2)，这次数据不够强，可以卡过去
class solution {
public:
int tr[50005][26];
int tot;
int val[50005];
void add(string s, int c){
int root = 0;
for(int i = 0; i < s.size(); ++i){
int id = s[i] - 'a';
if(!tr[root][id])tr[root][id] = ++tot;
root = tr[root][id];
}
if(val[root] == -1)val[root] = c;
else val[root] = min(val[root], c);
}
int minimumcost(string target, vector<string>& words, vector<int>& costs) {
tot = 0;
memset(val, -1,sizeof(val));
for(int i = 0; i < words.size(); ++i)
add(words[i], costs[i]);
vector<int>dp(target.size() + 1, 1e9);
dp[0] = 0;
for(int i = 0; i < target.size(); ++i){
int root = 0;
for(int j = i; j < target.size(); ++j){
int id = target[j] - 'a';
if(tr[root][id] == 0)break;
root = tr[root][id];
if(val[root] != -1){
dp[j + 1] = min(dp[j + 1], dp[i] + val[root]);
}
}
}
if(dp[target.size()] == 1e9)return -1;
else return dp[target.size()];
}
};
还有一种字符串哈希的方法，不过也不是正解
思路是，进行状态转移的时候，我们不是从
i
i
i 枚举到
n
n
n进行匹配，而是枚举可能的长度，统计一下所有
w
o
r
d
word
word的长度，由于题目保证所有 words[i].length 的总和小于或等于 50000，所以最坏情况长度是1 2 3 4….，不同长度的字符串的数量最大是
50000
\sqrt{50000}
50000,最多就两百多不同长度的字符串，只需要枚举这个，然后想一个
o
(
1
)
o(1)
o(1)的方法获取长度为len的字符串中能匹配
t
a
r
g
e
t
[
i
]
target[i]
target[i]到
t
a
r
g
e
t
[
i
+
l
e
n
−
1
]
target[i+len-1]
target[i+len−1]的字符串，这个可以用哈希来实现，对于每个长度，我们都开一个unordered_map存字符串的哈希值和费用，然后对
t
r
a
g
e
t
traget
traget也进行哈希处理，判匹配的时候就可以利用哈希o(1)计算
一个小技巧是，对于“体型”很大的stl结构需要多次遍历时，可以传引用参数，避免每次遍历都要复制一遍，跑的会快一些
比如，for(auto [len, x] : mp) 和 for(auto& [len, x] : mp)
-
for(auto [len, x] : mp)：这种写法会从容器
mp中获取每对键值对（key-value pair），并对它们进行复制。也就是说，[len, x]是对每个元素的拷贝。如果对len或x的修改不会影响到容器中原始的值。 -
for(auto& [len, x] : mp)：这种写法使用引用，因此不会对容器中的元素进行拷贝，而是直接引用容器中的元素。在这种情况下，
[len, x]是对容器中每个元素的引用。如果在循环体内修改len或x，将直接修改容器中相应的值。
class solution {
public:
const int mod = 1070777777;
const int base = 1331;
int minimumcost(string target, vector<string>& words, vector<int>& costs) {
int n = words.size(), m = target.size();
vector<int>hs(m + 1), mul(m + 1);
mul[0] = 1;
for(int i = 1; i <= m; ++i){
mul[i] = ((long long)mul[i - 1] * base)%mod;
hs[i] = ((long long)hs[i - 1] * base + target[i - 1])%mod;
}
map<int, unordered_map<int, int>>mp;
for(int i = 0; i < n; ++i){
int len = words[i].size();
long long h = 0;
for(int j = 0; j < len; ++j)
h = (h * base + words[i][j])%mod;
if(!mp[len].count(h))
mp[len][h] = costs[i];
else
mp[len][h] = min(mp[len][h], costs[i]);
}
vector<int>dp(m + 1, 1e9);
dp[0] = 0;
for(int i = 1; i <= m; ++i){
for(auto& [len, x] : mp){
int j = i + len - 1;
if(j > m)break;
long long h = ((long long)hs[j] - ((long long)hs[i - 1] * mul[len])%mod + mod) % mod;
if(x.count(h)){
dp[j] = min(dp[j], dp[i - 1] + x[h]);
}
}
}
if(dp[m] == 1e9)return -1;
else return dp[m];
}
};
发表评论