题目见{:target=”_blank”}
yxc code{:target=”_blank”}
C++ 代码
第一版 TLE 的代码,同时只使用 board 作为状态标记有点问题
class Solution {
public:
int findMinStep(string board, string hand) {
for(char c:hand)cnt_[c]++;
dfs(board);
if(res_ >= 6)return -1;
else return res_;
}
string clean_up(string board) {
bool run = true;
while(run) {
run = false;
for(int i=0; i<board.size();) {
int j = i+1;
while(j<board.size() && board[j] == board[i])j++;
if(j-i >= 3) {
board = board.substr(0,i) + board.substr(j);
run = true;
break;
}
i = j;
}
}
return board;
}
void dfs(string board) {
string s = board;
for(auto cnt : cnt_) {
char c = cnt.first;
int num = cnt.second;
if(num) {
--cnt_[c];
// 尝试将c添加到每一个位置
for(int i=0; i<=board.size(); ++i) {
s = board.substr(0, i) + c + board.substr(i);
s = clean_up(s);
if(dp_.count(s) == 0 || dp_[s] > dp_[board] + 1){
dp_[s] = dp_[board] + 1;
// 全部消除了
if(s == "")res_ = min(res_, dp_[s]);
dfs(s);
}
}
++cnt_[c];
}
}
}
private:
unordered_map<char, int> cnt_;
unordered_map<string, int> dp_; // 记忆化搜索
int res_ = 6;
};