488. 祖玛游戏 :「搜刮 + 剪枝」&「AStar 算法」

标题问题描述

那是 LeetCode 上的 「488. 祖玛游戏」 ，难度为 「困难」。

Tag : 「DFS」、「搜刮」、「启发式搜刮」

你正在参与祖玛游戏的一个变种。

在那个祖玛游戏变体中，桌面上有 一排 彩球，每个球的颜色可能是：红色 R、黄色 Y、蓝色 B、绿色 G 或白色 W 。你的手中也有一些彩球。

你的目的是 清空 桌面上所有的球。每一回合：

从你手上的彩球中选出 肆意一颗 ，然后将其插入桌面上那一排球中：两球之间或那一排球的任一端。接着，若是有呈现 三个或者三个以上 且 颜色不异 的球相连的话，就把它们移除掉。 若是那种移除操做同样招致呈现三个或者三个以上且颜色不异的球相连，则能够继续移除那些球，曲到不再满足移除前提。

若是桌面上所有球都被移除，则认为你博得本场游戏。反复那个过程，曲到你赢了游戏或者手中没有更多的球。

给你一个字符串 board ，暗示桌面上最起头的那排球。另给你一个字符串 hand ，暗示手里的彩球。请你按上述操做步调移除掉桌上所有球，计算并返回所需的 起码 球数。若是不克不及移除桌上所有的球，返回 -1 。

示例 1：

输入：board = "WRRBBW", hand = "RB" 输出：-1 解释：无法移除桌面上的所有球。能够得到的更好场面是： - 插入一个 R ，使桌面变成 WRRRBBW 。WRRRBBW -> WBBW - 插入一个 B ，使桌面变成 WBBBW 。WBBBW -> WW 桌面上还剩着球，没有其他球能够插入。

示例 2：

输入：board = "WWRRBBWW", hand = "WRBRW" 输出：2 解释：要想清空桌面上的球，能够按下述步调： - 插入一个 R ，使桌面变成 WWRRRBBWW 。WWRRRBBWW -> WWBBWW - 插入一个 B ，使桌面变成 WWBBBWW 。WWBBBWW -> WWWW -> empty 只需从手中出 2 个球就能够清空桌面。

示例 3：

输入：board = "G", hand = "GGGGG" 输出：2 解释：要想清空桌面上的球，能够按下述步调： - 插入一个 G ，使桌面变成 GG 。 - 插入一个 G ，使桌面变成 GGG 。GGG -> empty 只需从手中出 2 个球就能够清空桌面。

示例 4：

输入：board = "RBYYBBRRB", hand = "YRBGB" 输出：3 解释：要想清空桌面上的球，能够按下述步调： - 插入一个 Y ，使桌面变成 RBYYYBBRRB 。RBYYYBBRRB -> RBBBRRB -> RRRB -> B - 插入一个 B ，使桌面变成 BB 。 - 插入一个 B ，使桌面变成 BBB 。BBB -> empty 只需从手中出 3 个球就能够清空桌面。

提醒：

1 <= board.length <= 161 <= hand.length <= 5board 和 hand 由字符 R、Y、B、G 和 W 构成桌面上一起头的球中，不会有三个及三个以上颜色不异且连着的球搜刮 + 剪枝

数据范畴

代码：

class Solution { int INF = 0x3f3f3f3f; String b; int m; Map<String, Integer> map = new HashMap<>(); public int findMinStep(String a, String _b) { b = _b; m = b.length(); int ans = dfs(a, 1 << m); return ans == INF ? -1 : ans; } int dfs(String a, int cur) { if (a.length() == 0) return 0; if (map.containsKey(a)) return map.get(a); int ans = INF; int n = a.length(); for (int i = 0; i < m; i++) { if (((cur >> i) & 1) == 1) continue; int next = (1 << i) | cur; for (int j = 0; j <= n; j++) { boolean ok = false; if (j > 0 && j < n && a.charAt(j) == a.charAt(j - 1) && a.charAt(j - 1) != b.charAt(i)) ok = true; if (j < n && a.charAt(j) == b.charAt(i)) ok = true; if (!ok) continue; StringBuilder sb = new StringBuilder(); sb.append(a.substring(0, j)).append(b.substring(i, i + 1)); if (j != n) sb.append(a.substring(j)); int k = j; while (0 <= k && k < sb.length()) { char c = sb.charAt(k); int l = k, r = k; while (l >= 0 && sb.charAt(l) == c) l--; while (r < sb.length() && sb.charAt(r) == c) r++; if (r - l - 1 >= 3) { sb.delete(l + 1, r); k = l >= 0 ? l : r; } else { break; } } ans = Math.min(ans, dfs(sb.toString(), next) + 1); } } map.put(a, ans); return ans; } } 时间复杂度：略。「爆搜」同时还得考虑「剪枝」的复杂度阐发意义不大。空间复杂度：略AStar 算法

我们成立一个类 Node 来代指当前搜刮场面。

class Node { // 当前的棋盘情况 String a; // cur 代表当前 hand 的利用情况（若 cur 二进造暗示中的第 k 位为 1，代表 hand 的第 k 个彩球已被利用） // val 代表「当前棋盘为 a」和「hand 利用情况为 cur」的情况下，至少还需要几步才气将 a 全数消掉（启发式预算值） // step 代表当前场面是颠末几步而来 int cur, val, step; Node (String _a, int _c, int _v, int _s) { a = _a; cur = _c; val = _v; step = _s; } }

显然，间接对此停止 BFS，会 TLE。

我们考虑将优化 BFS 中利用到的队列改为优先队列：更接近谜底的场面先出队停止场面延展。

然后我们考虑若何设想 AStar 的启发式函数。

起首，一个合格的 AStar 启发式函数应当可以确保「估值不会小于理论最小间隔」。同时因为启发式的估值函数是针关于最末形态停止预算，因而只确保最末形态的第一次出队时为最短路，其余中间形态的初次出队纷歧定是最短路，为此我们需要利用哈希表来记录中间形态的间隔变革，若是某个场面的最短间隔被更新，我们应当将其再次入队。

基于此，我们设想如下的 AStar 的启发式函数：利用哈希表来统计「当前的棋盘 a 的彩球数量」&「当前手上拥有的彩球数量」，对「无解情况」和「理论最小次数」停止阐发：

关于某个彩球 c 而言，若是当前棋盘的数量 + 手上的数量 都不敷 3 个，那么该场面往下搜刮也一定无解，该场面无须入队；关于某个彩球 c 而言，若是当前棋盘数量少于 3 个，那么至少需要弥补至 3 个才气被消弭，而贫乏的个数则是「从手上彩球放入棋盘内」的次数，即关于彩球 c，我们理论上至少需要消耗 3 - cnt 次（cnt 为当前棋盘拥有的彩球 c 的数量）。

需要留意的是：关于某个场面 node 而言，最末的间隔是由「已确定间隔」+「估值间隔」两部门构成，我们应当按照那两部门之和停止出队，才气确保算法的准确性。

代码：

class Solution { class Node { String a; int cur, val, step; Node (String _a, int _c, int _v, int _s) { a = _a; cur = _c; val = _v; step = _s; } } int f(String a, int k) { Map<Character, Integer> m1 = new HashMap<>(), m2 = new HashMap<>(); for (int i = 0; i < a.length(); i++) { m1.put(a.charAt(i), m1.getOrDefault(a.charAt(i), 0) + 1); } for (int i = 0; i < m; i++) { if (((k >> i) & 1) == 0) m2.put(b.charAt(i), m2.getOrDefault(b.charAt(i), 0) + 1); } int ans = 0; for (char c : m1.keySet()) { int c1 = m1.get(c), c2 = m2.getOrDefault(c, 0); if (c1 + c2 < 3) return INF; if (c1 < 3) ans += (3 - c1); } return ans; } int INF = 0x3f3f3f3f; String b; int m; Map<String, Integer> map = new HashMap<>(); public int findMinStep(String _a, String _b) { b = _b; m = b.length(); PriorityQueue<Node> q = new PriorityQueue<>((o1,o2)->(o1.val+o1.step)-(o2.val+o2.step)); q.add(new Node(_a, 1 << m, f(_a, 1 << m), 0)); map.put(_a, 0); while (!q.isEmpty()) { Node poll = q.poll(); String a = poll.a; int cur = poll.cur; int step = poll.step; int n = a.length(); for (int i = 0; i < m; i++) { if (((cur >> i) & 1) == 1) continue; int next = (1 << i) | cur; for (int j = 0; j <= n; j++) { boolean ok = false; if (j > 0 && j < n && a.charAt(j) == a.charAt(j - 1) && a.charAt(j - 1) != b.charAt(i)) ok = true; if (j < n && a.charAt(j) == b.charAt(i)) ok = true; if (!ok) continue; StringBuilder sb = new StringBuilder(); sb.append(a.substring(0, j)).append(b.substring(i, i + 1)); if (j != n) sb.append(a.substring(j)); int k = j; while (0 <= k && k < sb.length()) { char c = sb.charAt(k); int l = k, r = k; while (l >= 0 && sb.charAt(l) == c) l--; while (r < sb.length() && sb.charAt(r) == c) r++; if (r - l - 1 >= 3) { sb.delete(l + 1, r); k = l >= 0 ? l : r; } else { break; } } String nextStr = sb.toString(); if (nextStr.length() == 0) return step + 1; if (f(nextStr, next) == INF) continue; if (!map.containsKey(nextStr) || map.get(nextStr) > step + 1) { map.put(nextStr, step + 1); q.add(new Node(nextStr, next, f(nextStr, next), step + 1)); } } } } return -1; } } 时间复杂度：略。「爆搜」同时还得考虑「启发式加速」的复杂度阐发意义不大。空间复杂度：略最初

那是我们「刷穿 LeetCode」系列文章的第 No.488 篇，系列起头于 2021/01/01，截行于起始日 LeetCode 上共有 1916 道标题问题，部门是有锁题，我们将先把所有不带锁的标题问题刷完。

在那个系列文章里面，除了讲解解题思绪以外，还会尽可能给出最为简洁的代码。若是涉及通解还会响应的代码模板。

为了便利列位同窗可以电脑长进行调试和提交代码，我成立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的响应代码、LeetCode 原题链接和其他优选题解。