作者推荐
本文涉及知识点
状态压缩
LeetCode:691 贴纸拼词
我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。
注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。
示例 1：
输入： stickers = [“with”,“example”,“science”], target = “thehat”
输出：3
解释：
我们可以使用 2 个 “with” 贴纸，和 1 个 “example” 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。
示例 2:
输入：stickers = [“notice”,“possible”], target = “basicbasic”
输出：-1
解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。
提示:
n == stickers.length
1 <= n <= 50
1 <= stickers[i].length <= 10
1 <= target.length <= 15
stickers[i] 和 target 由小写英文单词组成
封装类
假定target串有个n1字符，数量分别为m_vMax[0] m_vMax[1]…m_vMax[n1-1]。
对于某个stickers串，忽略target中没有的字符。target第0 1 2… 个字符在sticker的数量为vNum[0],vNum[1]…
则第0个字符的mask为1*vNum[0]
第1个字符的mask为(m_vMax[0]+1)*vNum[1]
…
第i个字符的mask为：Mul[ 0 , i − 1 ] j \Large^j_{[0,i-1]}[0,i−1]j(vMax[j]+1)*vNum[i]
总mask 为各字符mask之和。
注意： 无论如何vNum[i]都大于等于0，小于等于m_vMax[i]
class CMask { public: void Add(int iMax)//当前最高位范围[0,iMax] { m_vMax.emplace_back(iMax); m_iMaskCount *= (iMax + 1); } vector<int> FromMask(int iMask) { vector<int> vNums; for (int i = 0; i < m_vMax.size(); i++) { vNums.emplace_back(iMask % (m_vMax[i] + 1)); iMask /= (m_vMax[i] + 1); } return vNums; } int ToMask(const vector<int>& vNums,int iMul=1) { int iMask = 0; int iUnit = 1; for (int i = 0; i < m_vMax.size(); i++) { iMask += iUnit * min(m_vMax[i],vNums[i]* iMul); iUnit *= (m_vMax[i]+1); } return iMask; } int MaskSubVector(int iMask, const vector<int>& vNums, const int iMul = 1) { int iNewMask = 0; int iUnit = 1; for (int i = 0; i < m_vMax.size(); i++) { int cur = iMask % (m_vMax[i] + 1); cur -= vNums[i] * iMul; cur = max(0, cur); iNewMask += iUnit * cur; iMask /= (m_vMax[i] + 1); iUnit *= (m_vMax[i]+1); } return iNewMask; } int NeedGroupCount(const vector<int>& need, const vector<int>& has) { int iMax = 0; for (int i = 0; i < m_vMax.size(); i++) { if (has[i] <= 0) { continue; } iMax = max(iMax,need[i] / has[i]+ (0 != need[i] % has[i])); } return iMax; } public: int MaskCount()const { return m_iMaskCount; } int BitCount()const { return m_vMax.size(); } protected: int m_iMaskCount = 1; vector<int> m_vMax; }; class CStrMask : public CMask { public: CStrMask(const string& target) { vector<int> vCount; for (const auto& ch : target) { if (mCharToIndex.count(ch)) { vCount[mCharToIndex[ch]]++; } else { mCharToIndex[ch] = vCount.size(); vCount.emplace_back(1); } } for (const auto& cnt : vCount) { CMask::Add(cnt); } } vector<int> GetVector(const string& s ) { vector<int> vCharNums(m_vMax.size()); for (const char& ch : s) { if (mCharToIndex.count(ch)) { auto& i = vCharNums[mCharToIndex[ch]]; if (i < m_vMax[mCharToIndex[ch]]) { i++; } } } return vCharNums; } protected: unordered_map<char, int> mCharToIndex; private: void Add(int iMax) {}; };
动态规划
动态规划的状态表示
pre[iMask] 表示利用前i-1个贴纸，达到未完成的字符状态为iMask的消耗的最少贴纸数。1000表示无法达成。
dp[iMask] 表示利用前i 个贴纸，达到未完成的字符状态为iMask的消耗的最少贴纸数。
动态规划的转移方程
iPreMask 当前贴纸 使用的贴纸数量 如果状态发生变化，则更新状态。
动态规划的填表顺序
对于每个合法的iPreMask，计算当前贴纸最多需要多少份。三层循环：第一层，枚举各贴纸。第二层，枚举pre各状态。第三层：枚举当前贴纸使用的数量。每次处理还要枚举各字符。
故总时间复杂度为：O(50*2151515)
动态规划的初始状态
pre[iMaskCount-1=0 其它值为1000。
动态规划的返回值
pre[0]
代码
核心代码
class Solution { public: int minStickers(vector<string>& stickers, string target) { CStrMask mask(target); vector<vector<int>> vMaskToCounts(mask.MaskCount()); for (int i = 0; i < mask.MaskCount(); i++) { vMaskToCounts[i] = mask.FromMask(i); } vector<int> vPre(mask.MaskCount(), 1000); vPre[mask.MaskCount() - 1] = 0; for (const auto s : stickers) { auto vCharNums = mask.GetVector(s); vector<int> dp = vPre;//不选择 for (int iPre = 0; iPre < mask.MaskCount(); iPre++) { if (vPre[iPre] >= 1000) { continue; } const int iSelMax = mask.NeedGroupCount(vMaskToCounts[iPre], vCharNums); for (int iSel = 1; iSel <= iSelMax; iSel++) { const int iNewMask = mask.MaskSubVector(iPre, vCharNums, iSel); dp[iNewMask] = min(dp[iNewMask], vPre[iPre] + iSel); } } vPre.swap(dp); } return (vPre[0] >= 1000) ? -1 : vPre[0]; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<string> stickers; string target; { Solution sln; stickers = { "travel", "quotient", "nose", "wrote", "any" }, target = "lastwest"; auto res = sln.minStickers(stickers, target); Assert(4, res); } { Solution sln; stickers = { "with", "example", "science" }, target = "thehat"; auto res = sln.minStickers(stickers, target); Assert(3, res); } { Solution sln; stickers = { "notice", "possible" }, target = "basicbasic"; auto res = sln.minStickers(stickers, target); Assert(-1, res); } { Solution sln; stickers = { "right", "ten", "year", "share", "period", "paper", "expect", "village", "home", "happen", "ring", "sat", "even", "afraid", "paint", "self", "range", "camp", "note", "read", "paragraph", "run", "basic", "fill", "week", "his", "star", "power", "any", "colony", "object", "free", "dark", "said", "chick", "true", "glad", "child", "room", "lost", "am", "cry", "quiet", "crease", "while", "race", "fun", "found", "dream", "once" }, target = "materialhalf"; auto res = sln.minStickers(stickers, target); Assert(4, res); } { Solution sln; stickers = { "indicate","why","finger","star","unit","board","sister","danger","deal","bit","phrase","caught","if","other","water","huge","general","read","gold","shall","master","men","lay","party","grow","view","if","pull","together","head","thank","street","natural","pull","raise","cost","spoke","race","new","race","liquid","me","please","clear","could","reply","often","huge","old","nor" }, target = "fhhfiyfdcwbycma"; auto res = sln.minStickers(stickers, target); Assert(9, res); } }
改进简洁版，性能略差
不区分dp pre，因为一个贴纸可以无限使用。无论是pre[iMask]和dp[iMask] 都可增加贴纸。
动态规划的状态表示
状态压缩：如果target第i位已经贴好，则此位为1；否则此位为0。
dp[iMask] 已经完成iMask 消耗的最少贴纸数。
动态规划的转移方程。
对应每个mask，只需要考虑一个当前贴纸。比如： 目标串为aaa，贴纸为a。状态0只考虑一个贴纸。状态1只考虑1个贴纸，总共2个贴纸。状态3只考虑1个贴纸，总共3个贴纸。
如果目标串有多个相同字符，只需要匹配第一字符。“???” 第一张贴纸后，变成"a??" 不需要考虑“?a?"
方案一：第i步匹配第1个a，第j个步匹配第2个a。
方案二：第i步匹配第2个a，第j个步匹配第1个a。
如果方案二，能达到目标，那方案一显然也能达到目标。
iPreMask等于iNewMask 也不用排除，因为新值比旧值大1，必定被淘汰。
class Solution { public: int minStickers(vector<string>& stickers, string target) { const int iMaskCount = 1 << target.size(); vector<int> dp(iMaskCount, 1000); dp[0] = 0; for (const auto s : stickers) { int cnt1[26] = { 0 }; for (const auto& ch : s) { cnt1[ch - 'a']++; } for (int iPreMask = 0; iPreMask < iMaskCount; iPreMask++) { int cnt[26] = { 0 }; memcpy(cnt, cnt1, sizeof(cnt1)); int iNewMask = iPreMask; for (int j = 0; j < target.size(); j++) { if (iPreMask & (1 << j)) { continue;//已经拼成 } if (cnt[target[j] - 'a']) { cnt[target[j] - 'a']--; iNewMask |= (1 << j); } } dp[iNewMask] = min(dp[iNewMask], dp[iPreMask] + 1); } } return (dp.back() >= 1000) ? -1 : dp.back(); } };
2023年1月第一版
class Solution {
public:
int minStickers(vector& stickers, string target) {
m_target = target;
for (auto& ch : target)
{
m_mTarget[ch]++;
}
std::unordered_set hasMask;
hasMask.insert(0);
std::unordered_map<int,int> preMaskNum;
preMaskNum[0] = 0;
for (auto& s : stickers)
{
std::unordered_map<char, int> mCur;
for (auto& ch : s)
{
if (m_mTarget.count(ch))
{
mCur[ch]++;
}
}
std::unordered_map<int, int> dp = preMaskNum;
const int iCurMask = MakeMask(mCur);
if (hasMask.count(iCurMask))
{
continue;
}
hasMask.insert(iCurMask);
for (const auto& preMask : preMaskNum )
{
std::unordered_map<char, int> mPre;
ParseMask(mPre, preMask.first);
bool bAdd = true;
int iNum = preMask.second;
while (bAdd)
{
bAdd = false;
for (const auto it : mCur)
{
if (m_mTarget[it.first] > mPre[it.first])
{
bAdd = true;
mPre[it.first] = min(m_mTarget[it.first], mPre[it.first] + mCur[it.first]);
}
}
if (bAdd)
{
iNum++;
const int iMask = MakeMask(mPre);
if (dp.count(iMask))
{
dp[iMask] = min(dp[iMask], iNum);
}
else
{
dp[iMask] = iNum;
}
}
}
}
preMaskNum.swap(dp);
}
int iMaskTargt = MakeMask(m_mTarget);
if (preMaskNum.end() == preMaskNum.find(iMaskTargt))
{
return -1;
}
return preMaskNum[iMaskTargt];
}
int MakeMask(const std::unordered_map<char, int>& nums)const
{
int iMask = 0;
for (const auto& mm : m_mTarget )
{
auto it = nums.find(mm.first);
if ((nums.end() != it) && ( it->second > 0 ))
{
iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
}
else
{
iMask = iMask * (mm.second + 1);
}
}
return iMask;
}
void ParseMask(std::unordered_map<char, int>& nums, int iMask)
{
int iMul = 1;
for (auto& it : m_mTarget)
{
iMul *= (it.second+1);
}
for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
{
iMul /= (it->second+1);
nums[it->first] = iMask / iMul;
iMask %= iMul;
}
}
std::string m_target;
std::unordered_map<char, int> m_mTarget;
};
2023年1月第2版
class Solution {
public:
int minStickers(vector& stickers, string target) {
m_target = target;
Init();
vector<std::unordered_map<char, int>> mAllCharNum;
{
std::unordered_set hasMask;
hasMask.insert(0);
for (int i = stickers.size() - 1; i >= 0; i–)
{
std::unordered_map<char, int> mCur;
for (auto& ch : stickers[i])
{
if (m_mTarget.count(ch))
{
mCur[ch]++;
}
}
const int iCurMask = MakeMask(mCur);
if (hasMask.count(iCurMask))
{
continue;
}
hasMask.insert(iCurMask);
mAllCharNum.push_back(mCur);
}
}
std::unordered_set setPreMask,setHasDo;
setPreMask.insert(m_iTargetMask);
setHasDo.insert(m_iTargetMask);
for (int iOpeNum = 1; iOpeNum <= target.length(); iOpeNum++)
{
std::unordered_set dp;
for (auto& preMask : setPreMask)
{
std::unordered_map<char, int> mPre;
ParseMask(mPre, preMask);
for (auto& mCur : mAllCharNum)
{
const int iSubMask = GetSubMask(mPre, mCur);
if (0 == iSubMask)
{
continue;
}
const int iNewMask = preMask - iSubMask;
if (setHasDo.count(iNewMask))
{
continue;
}
if (iNewMask == 0 )
{
return iOpeNum;
}
setHasDo.insert(iNewMask);
dp.insert(iNewMask);
}
}
setPreMask.swap(dp);
vector<std::unordered_map<char, int>> mAllTmp;
for (auto& it : setPreMask)
{
std::unordered_map<char, int> tmp;
ParseMask(tmp, it);
mAllTmp.push_back(tmp);
}
}
return -1;
}
int GetSubMask(const std::unordered_map<char, int>& mPre, const std::unordered_map<char, int>& mCur)
{
int iSubMask = 0;
for (auto& cur : mCur)
{
auto pre = mPre.find(cur.first);
if (pre->second )
{
iSubMask += min(pre->second, cur.second) * m_vCharMul[cur.first-‘a’];
}
}
return iSubMask;
}
int MakeMask(const std::unordered_map<char, int>& nums)const
{
int iMask = 0;
for (const auto& mm : m_mTarget )
{
auto it = nums.find(mm.first);
if ((nums.end() != it) && ( it->second > 0 ))
{
iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
}
else
{
iMask = iMask * (mm.second + 1);
}
}
return iMask;
}
void ParseMask(std::unordered_map<char, int>& nums, int iMask)
{
for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
{
const int iMul = m_vCharMul[it->first-‘a’];
nums[it->first] = iMask / iMul;
iMask %= iMul;
}
}
void Init()
{
for (auto& ch : m_target)
{
m_mTarget[ch]++;
}
m_iTargetMask = MakeMask(m_mTarget);
int iMul = 1;
for (auto& it : m_mTarget)
{
iMul *= (it.second + 1);
}
for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
{
iMul /= (it->second + 1);
m_vCharMul[it->first - ‘a’] = iMul;
}
}
std::string m_target;
int m_iTargetMask;
std::unordered_map<char, int> m_mTarget;
int m_vCharMul[26] ;
};
2023年1月第三版
class Solution {
public:
int minStickers(vector& stickers, string target) {
m_target = target;
Init();
vector<std::unordered_map<char, int>> mAllCharNum; { std::unordered_set<int> hasMask; hasMask.insert(0); for (int i = stickers.size() - 1; i >= 0; i--) { std::unordered_map<char, int> mCur; for (auto& ch : stickers[i]) { if (m_mTarget.count(ch)) { mCur[ch]++; } } const int iCurMask = MakeMask(mCur); if (hasMask.count(iCurMask)) { continue; } hasMask.insert(iCurMask); mAllCharNum.push_back(mCur); } } std::unordered_set<int> setPreMask,setHasDo; setPreMask.insert(m_iTargetMask); setHasDo.insert(m_iTargetMask); for (int iOpeNum = 1; iOpeNum <= target.length(); iOpeNum++) { std::unordered_set<int> dp; for (auto& preMask : setPreMask) { std::unordered_map<char, int> mPre; ParseMask(mPre, preMask); char chFristNeedChar = 0; for (auto& it : mPre) { if (it.second > 0) { chFristNeedChar = it.first; break; } } for (auto& mCur : mAllCharNum) { if ((0 == mCur.count(chFristNeedChar)) || (mCur[chFristNeedChar] <= 0 )) { continue; } const int iSubMask = GetSubMask(mPre, mCur); if (0 == iSubMask) { continue; } const int iNewMask = preMask - iSubMask; if (setHasDo.count(iNewMask)) { continue; } if (iNewMask == 0 ) { return iOpeNum; } setHasDo.insert(iNewMask); dp.insert(iNewMask); } } setPreMask.swap(dp); vector<std::unordered_map<char, int>> mAllTmp; for (auto& it : setPreMask) { std::unordered_map<char, int> tmp; ParseMask(tmp, it); mAllTmp.push_back(tmp); } } return -1; } int GetSubMask(const std::unordered_map<char, int>& mPre, const std::unordered_map<char, int>& mCur) { int iSubMask = 0; for (auto& cur : mCur) { auto pre = mPre.find(cur.first); if (pre->second ) { iSubMask += min(pre->second, cur.second) * m_vCharMul[cur.first-'a']; } } return iSubMask; } int MakeMask(const std::unordered_map<char, int>& nums)const { int iMask = 0; for (const auto& mm : m_mTarget ) { auto it = nums.find(mm.first); if ((nums.end() != it) && ( it->second > 0 )) { iMask = iMask * (mm.second + 1) + min(mm.second, it->second); } else { iMask = iMask * (mm.second + 1); } } return iMask; } void ParseMask(std::unordered_map<char, int>& nums, int iMask) { for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it) { const int iMul = m_vCharMul[it->first-'a']; nums[it->first] = iMask / iMul; iMask %= iMul; } } void Init() { for (auto& ch : m_target) { m_mTarget[ch]++; } m_iTargetMask = MakeMask(m_mTarget); int iMul = 1; for (auto& it : m_mTarget) { iMul *= (it.second + 1); } for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it) { iMul /= (it->second + 1); m_vCharMul[it->first - 'a'] = iMul; } } std::string m_target; int m_iTargetMask; std::unordered_map<char, int> m_mTarget; int m_vCharMul[26] ;
};
2023年1月 第4版
class CCTestHash
{
public:
std::size_t operator()(const std::unordered_map<char, int>& nums) const
{
return MakeMask(nums);
}
static int MakeMask(const std::unordered_map<char, int>& nums)
{
int iMask = 0;
for (const auto& mm : m_mTarget)
{
auto it = nums.find(mm.first);
if ((nums.end() != it) && (it->second > 0))
{
iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
}
else
{
iMask = iMask * (mm.second + 1);
}
}
return iMask;
}
static void Init() { m_mTarget.clear(); for (auto& ch : m_target) { m_mTarget[ch]++; } m_iTargetMask = MakeMask(m_mTarget); int iMul = 1; for (auto& it : m_mTarget) { iMul *= (it.second + 1); } for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it) { iMul /= (it->second + 1); m_vCharMul[it->first - 'a'] = iMul; } } static std::string m_target; static int m_iTargetMask; static std::unordered_map<char, int> m_mTarget; static int m_vCharMul[26];
};
std::string CCTestHash::m_target;
int CCTestHash::m_iTargetMask;
std::unordered_map<char, int> CCTestHash::m_mTarget;
int CCTestHash::m_vCharMul[26];
class Solution {
public:
int minStickers(vector& stickers, string target) {
CCTestHash::m_target = target;
CCTestHash::Init();
std::unordered_set<std::unordered_map<char, int>, CCTestHash> hasMask; { for (int i = stickers.size() - 1; i >= 0; i--) { std::unordered_map<char, int> mCur; for (auto& ch : stickers[i]) { if (m_testHask.m_mTarget.count(ch)) { mCur[ch]++; } } if (0 == mCur.size()) { continue; } if (hasMask.count(mCur)) { continue; } hasMask.insert(mCur); } } std::unordered_set<std::unordered_map<char, int>, CCTestHash> setPreMask, setHasDo; setPreMask.insert(CCTestHash::m_mTarget); setHasDo.insert(CCTestHash::m_mTarget); for (int iOpeNum = 1; iOpeNum <= target.length(); iOpeNum++) { std::unordered_set<std::unordered_map<char, int>, CCTestHash> dp; for (auto& mPre : setPreMask) { char chFristNeedChar = 0; for (auto& it : mPre) { if (it.second > 0) { chFristNeedChar = it.first; break; } } for (auto& mCur : hasMask) { if ((0 == mCur.count(chFristNeedChar)) || (mCur.find(chFristNeedChar)->second <= 0 )) { continue; } auto newMask = GetSubMask(mPre, mCur); if (setHasDo.count(newMask)) { continue; } if (CCTestHash::MakeMask(newMask) == 0) { return iOpeNum; } setHasDo.insert(newMask); dp.insert(newMask); } } setPreMask.swap(dp); } return -1; } std::unordered_map<char, int> GetSubMask(const std::unordered_map<char, int>& mPre, const std::unordered_map<char, int>& mCur) { std::unordered_map<char, int> vRet; for (auto& pre : mPre) { auto cur = mCur.find(pre.first); if (mCur.end() != cur) { vRet[pre.first] = max(0, pre.second - cur->second); } else { vRet[pre.first] = pre.second; } } return vRet; } /* int MakeMask(const std::unordered_map<char, int>& nums)const { int iMask = 0; for (const auto& mm : m_mTarget ) { auto it = nums.find(mm.first); if ((nums.end() != it) && ( it->second > 0 )) { iMask = iMask * (mm.second + 1) + min(mm.second, it->second); } else { iMask = iMask * (mm.second + 1); } } return iMask; } void ParseMask(std::unordered_map<char, int>& nums, int iMask) { for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it) { const int iMul = m_vCharMul[it->first-'a']; nums[it->first] = iMask / iMul; iMask %= iMul; } } */ CCTestHash m_testHask;
};
