# AC A* search solution

• ``````struct node
{
string board;
unordered_map<char, int> dict;
int g; // balls used
int f;
int balls;
node() = default;
node(string b, unordered_map<char, int> d, int depth, int c)
: board(b), dict(d), g(depth), balls(c)
{
unordered_set<char> s;
for (auto c : board) s.insert(c);
f = g + heurist();
};
int heurist()
{
unordered_set<char> s;
for (auto c : board) s.insert(c);
return board.length() * s.size();
}
};
class Solution
{
private:
void erase_3(string &s, int pos)
{
int start = pos;
for (; start >= 0 && s[start] == s[pos]; --start);
if (start == pos - 1) return;
int end = pos;
for (; end < s.length() && s[end] == s[pos]; ++end);
if (end - ++start >= 3)
{
s.erase(start, end - start);
erase_3(s, start);
}
}
public:
int findMinStep(string board, string hand)
{
unordered_map<char, int> dict;
for (auto &c : hand) ++dict[c];
node *root = new node(board, dict, 0, hand.length());
auto cmp = [](node *lhs, node *rhs) { return lhs->f > rhs->f; };
priority_queue<node*, vector<node*>, decltype(cmp)> open_lst(cmp);
open_lst.push(root);
unordered_map<string, int> dist;
dist[board] = 0;
unordered_set<string> cls_lst;
while (!open_lst.empty())
{
auto curr = open_lst.top();
open_lst.pop();
cls_lst.insert(curr->board);
string b = curr->board;
for (int i = 0; i < b.length();)
{
int count = 1;
while (i + count < b.length() && b[i] == b[i + count])
++count;
if (curr->dict[b[i]] < 3 - count)
{
i += count;
continue;
}
int gap = 3 - count; // balls would be used
string tmp = b;
tmp.erase(i, count);
curr->dict[b[i]] -= gap;
erase_3(tmp, i);
if (tmp.empty())
return curr->g + 3 - count;
auto neighbor =
new node(tmp, curr->dict, curr->g + gap, curr->balls - gap);
curr->dict[b[i]] += gap;
i += count;
if (cls_lst.count(tmp)
|| (dist.count(tmp) && dist[tmp] <= neighbor->g)
|| neighbor->balls == 0)
{
delete neighbor;
continue;
}
dist[tmp] = neighbor->g;
open_lst.push(neighbor);
}
}
return -1;
}
};
``````

I will try to make it more concise.

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.