题目链接：1255. 得分最高的单词集合
方法：暴力回溯
解题思路
观察可以发现，本题的数据量范围较小，使用暴力回溯不超过\(2^1\)\(^4\)次，需要注意的有，当选择一个单词时，必须保证当前提供的字符集合中剩余字符能够组成该单词\(check()\)，选择以后将字符集合中对应字符数量减少\(destroy()\)，回溯回来之后将其恢复\(resume()\)。
做题过程中的问题
- 当想使用记忆化搜索进行优化时，发现由于选择当前单词时需要进行判定，并减小字符集合中的字符数量，会导致 \(cache\) 数组的更新不准确；因为子问题与当前问题两者之间不是独立关系，子问题的选取会影响当前单词是否能选。
- 不要在开始对 \(words\) 数组中的单词分数进行预处理，因为 \(words\) 中出现的单词可以重复，那么可能最终求得分数是重复单词分数之和。
代码
class Solution {
public:
unordered_map<char, int> cnt; // 统计letters中字符出现的数量
bool check(string word) { // 检查单词word是否能被组成
unordered_map<char, int> temp_cnt;
for (auto &c : word) temp_cnt[c] ++ ;
for (auto &i : temp_cnt) {
if (cnt[i.first] < i.second) return false;
}
return true;
}
void destroy(string word) { // 当选择某个word时，要减小对应字母的数量
for (auto &c : word) cnt[c] -- ;
}
void resume(string word) { // 回溯时，恢复现场
for (auto &c : word) cnt[c] ++ ;
}
int dfs(vector<string>& words, vector<int>& score, int idx) {
if (idx < 0) return 0;
int temp1 = 0;
if (check(words[idx])) { // 选择当前word
destroy(words[idx]);
int wordScore = 0; // 计算当前word的得分
for (auto &c : words[idx]) wordScore += score[c - 'a'];
temp1 = dfs(words, score, idx - 1) + wordScore;
resume(words[idx]);
}
return max(temp1, dfs(words, score, idx - 1)); // 在选择当前word 和 不选择两种情况中取最大值
}
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
for (auto &c : letters) cnt[c] ++ ;
return dfs(words, score, words.size() - 1);
}
};
复杂度分析
时间复杂度：\(O(m + L * 2^n)\)，\(m\) 为 \(letters\) 数组长度，\(L\) 为 \(words[i]\) 的长度，\(n\) 为 \(words\) 数组长度；
空间复杂度：\(O(\Sigma)\)，\(\Sigma\)为所有字符集合的大小，本题限定为小写字母，故\(\Sigma = 26\)