golang 解法, 执行用时: 240 ms, 内存消耗: 28 MB, 提交时间: 2023-10-27 00:04:24

type state struct {
    board string
    hand [5]int
}

func findMinStep(board string, hand string) int {
    cache := map[string]string{}
    COLORS := "RYBGW"

    var clean func(b string) string
    clean = func(board string) string {
        if v, ok := cache[board]; ok {
            return v
        } 
        res := board
        for i, j := 0, 0; i < len(board); {
            for j < len(board) && board[i] == board[j] {
                j += 1
            }
            if j - i > 2 {
                res = clean(board[:i] + board[j:])
                cache[board] = res
                return res
            }
            i = j
        }
        cache[board] = res
        return res
    }

    cnts := func(hand string) [5]int {
        res := [5]int{}
        for i := 0; i < len(hand); i++ {
            for j, c := range COLORS {
                if hand[i] == byte(c) {
                    res[j]++
                    break
                }
            }
        }
        return res
    }

    queue := make([]state, 0, 6)
    init := state{board, cnts(hand)}
    queue = append(queue, init)
    visited := map[state]int{}
    visited[init] = 0
    for len(queue) > 0 {
        curState := queue[0]
        cur_board, cur_hand := curState.board, curState.hand
        if len(cur_board) == 0 {
            return visited[curState]
        }
        queue = queue[1:]
        for i := 0; i <= len(cur_board) ; i++ {
            for j, r := range COLORS {
                if cur_hand[j] > 0 {
                    c := byte(r)
                    // 第 1 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球(在它前面插入过了，不需要再插入，意义相同)
                    if i > 0 && cur_board[i - 1] == c{
                        continue
                    }

                    /** 
                     *  第 2 个剪枝条件: 只在以下两种情况放置新球
                     *  - 第 1 种情况 : 当前后颜色相同且与当前颜色不同时候放置球
                     *  - 第 2 种情况 : 当前球颜色与后面的球的颜色相同
                     */
                    choose := false
                    if 0 < i && i < len(cur_board) && cur_board[i - 1] == cur_board[i] && cur_board[i - 1] != c{
                        choose = true
                    }
                    if i < len(cur_board) && cur_board[i] == c{
                        choose = true
                    }
                    
                    if choose {
                        nxt := [5]int{}
                        for k,_ := range COLORS{
                            nxt[k] = cur_hand[k]
                        }
                        nxt[j] -= 1
                        
                        nextState := state{clean(cur_board[:i] + string(c) + cur_board[i:]), nxt}
                        if _,ok := visited[nextState]; !ok {
                            queue = append(queue, nextState)
                            visited[nextState] = visited[curState] + 1
                        }
                    }
                }
            }
        }
    }
    return -1
}

python3 解法, 执行用时: 1796 ms, 内存消耗: 42 MB, 提交时间: 2023-10-27 00:03:46

import re
from functools import lru_cache
from itertools import product

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        ans = self.dfs(board, "".join(sorted(hand)))
        return ans if ans <= 5 else -1

    @lru_cache(None)
    def dfs(self, cur_board: str, cur_hand: str):
        if not cur_board:
            return 0
        
        res = 6
        for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):
            # 第 1 个剪枝条件: 手中颜色相同的球只需要考虑其中一个即可
            if j > 0 and cur_hand[j] == cur_hand[j - 1]:
                continue

            # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球
            if i > 0 and cur_board[i - 1] == cur_hand[j]:
                continue

            # 第 3 个剪枝条件: 只考虑放置新球后有可能得到更优解的位置
            choose = False
            #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同
            if i < len(cur_board) and cur_board[i] == cur_hand[j]:
                choose = True
            #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球
            if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:
                choose = True
            
            if choose:
                new_board = self.clean(cur_board[:i] + cur_hand[j] + cur_board[i:])
                new_hand = cur_hand[:j] + cur_hand[j + 1:]
                res = min(res, self.dfs(new_board, new_hand) + 1)
        return res

    @staticmethod
    def clean(s):
        n = 1
        while n:
            s, n = re.subn(r'(.)\1{2,}', '', s)
        return s

python3 解法, 执行用时: 1232 ms, 内存消耗: 26.4 MB, 提交时间: 2023-10-27 00:03:34

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        def clean(s):
            # 消除桌面上需要消除的球
            n = 1
            while n:
                s, n = re.subn(r"(.)\1{2,}", "", s)
            return s

        hand = "".join(sorted(hand))

        # 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数
        queue = deque([(board, hand, 0)])

        # 初始化用哈希集合维护的已访问过的状态
        visited = {(board, hand)}

        while queue:
            cur_board, cur_hand, step = queue.popleft()
            for i, j in product(range(len(cur_board) + 1), range(len(cur_hand))):
                # 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同
                if j > 0 and cur_hand[j] == cur_hand[j - 1]:
                    continue

                # 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球
                if i > 0 and cur_board[i - 1] == cur_hand[j]:
                    continue
                
                # 第 3 个剪枝条件: 只在以下两种情况放置新球
                choose = False
                #  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同
                if i < len(cur_board) and cur_board[i] == cur_hand[j]:
                    choose = True
                #  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球
                if 0 < i < len(cur_board) and cur_board[i - 1] == cur_board[i] and cur_board[i - 1] != cur_hand[j]:
                    choose = True

                if choose:
                    new_board = clean(cur_board[:i] + cur_hand[j] + cur_board[i:])
                    new_hand = cur_hand[:j] + cur_hand[j + 1:]
                    if not new_board:
                        return step + 1
                    if (new_board, new_hand) not in visited:
                        queue.append((new_board, new_hand, step + 1))
                        visited.add((new_board, new_hand))

        return -1

cpp 解法, 执行用时: 1424 ms, 内存消耗: 369.9 MB, 提交时间: 2023-10-27 00:03:21

struct State {
    string board;
    string hand;
    int step;
    State(const string & board, const string & hand, int step) {
        this->board = board;
        this->hand = hand;
        this->step = step;
    }
};

class Solution {
public:
    string clean(const string & s) {
        string res;
        vector<pair<char, int>> st;
        
        for (auto c : s) {
            while (!st.empty() && c != st.back().first && st.back().second >= 3) {
                st.pop_back();
            }
            if (st.empty() || c != st.back().first) {
                st.push_back({c,1});
            } else {
                st.back().second++;
            }
        }
        if (!st.empty() && st.back().second >= 3) {
            st.pop_back();
        }
        for (int i = 0; i < st.size(); ++i) {
            for (int j = 0; j < st[i].second; ++j) {
                res.push_back(st[i].first);
            }
        }
        return res;
    }

    int findMinStep(string board, string hand) {
        unordered_set<string> visited;
        sort(hand.begin(), hand.end());

        visited.insert(board + " " + hand);
        queue<State> qu;
        qu.push(State(board, hand, 0));
        while (!qu.empty()) {
            State curr = qu.front();
            qu.pop();

            for (int j = 0; j < curr.hand.size(); ++j) {
                // 第 1 个剪枝条件: 当前选择的球的颜色和前一个球的颜色相同
                if (j > 0 && curr.hand[j] == curr.hand[j - 1]) {
                    continue;
                }
                for (int i = 0; i <= curr.board.size(); ++i) {
                    // 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球
                    if (i > 0 && curr.board[i - 1] == curr.hand[j]) {
                        continue;
                    }

                    // 第 3 个剪枝条件: 只在以下两种情况放置新球
                    bool choose = false;
                    //   第 1 种情况 : 当前球颜色与后面的球的颜色相同
                    if (i < curr.board.size() && curr.board[i] == curr.hand[j]) {
                        choose = true;
                    }  
                    //   第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球
                    if (i > 0 && i < curr.board.size() && curr.board[i - 1] == curr.board[i] && curr.board[i] != curr.hand[j]){
                        choose = true;
                    }
                    if (choose) {
                        string new_board = clean(curr.board.substr(0, i) + curr.hand[j] + curr.board.substr(i));
                        string new_hand = curr.hand.substr(0, j) + curr.hand.substr(j + 1);
                        if (new_board.size() == 0) {
                            return curr.step + 1;
                        }
                        if (!visited.count(new_board + " " + new_hand)) {
                            qu.push(State(new_board, new_hand, curr.step + 1));
                            visited.insert(new_board + " " + new_hand);
                        }
                    }
                }
            }
        }

        return -1;  
    }
};

java 解法, 执行用时: 654 ms, 内存消耗: 54.3 MB, 提交时间: 2023-10-27 00:02:53

class Solution {
    Map<String, Integer> dp = new HashMap<String, Integer>();

    public int findMinStep(String board, String hand) {
        char[] arr = hand.toCharArray();
        Arrays.sort(arr);
        hand = new String(arr);
        int ans = dfs(board, hand);
        return ans <= 5 ? ans : -1;
    }

    public int dfs(String board, String hand) {
        if (board.length() == 0) {
            return 0;
        }
        String key = board + " " + hand;
        if (!dp.containsKey(key)) {
            int res = 6;
            for (int j = 0; j < hand.length(); ++j) {
                // 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同
                if (j > 0 && hand.charAt(j) == hand.charAt(j - 1)) {
                    continue;
                }
                for (int i = 0; i <= board.length(); ++i) {
                    // 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球
                    if (i > 0 && board.charAt(i - 1) == hand.charAt(j)) {
                        continue;
                    }

                    // 第 3 个剪枝条件: 只在以下两种情况放置新球
                    boolean choose = false;
                    //  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同
                    if (i < board.length() && board.charAt(i) == hand.charAt(j)) {
                        choose = true;
                    }
                    //  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球
                    if (i > 0 && i < board.length() && board.charAt(i - 1) == board.charAt(i) && board.charAt(i - 1) != hand.charAt(j)) {
                        choose = true;
                    }

                    if (choose) {
                        String newBoard = clean(board.substring(0, i) + hand.charAt(j) + board.substring(i));
                        String newHand = hand.substring(0, j) + hand.substring(j + 1);
                        res = Math.min(res, dfs(newBoard, newHand) + 1);
                    }
                }
            }
            dp.put(key, res);
        }
        return dp.get(key);
    }

    public String clean(String s) {
        StringBuffer sb = new StringBuffer();
        Deque<Character> letterStack = new ArrayDeque<Character>();
        Deque<Integer> countStack = new ArrayDeque<Integer>();
        
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            while (!letterStack.isEmpty() && c != letterStack.peek() && countStack.peek() >= 3) {
                letterStack.pop();
                countStack.pop();
            }
            if (letterStack.isEmpty() || c != letterStack.peek()) {
                letterStack.push(c);
                countStack.push(1);
            } else {
                countStack.push(countStack.pop() + 1);
            }
        }
        if (!countStack.isEmpty() && countStack.peek() >= 3) {
            letterStack.pop();
            countStack.pop();
        }
        while (!letterStack.isEmpty()) {
            char letter = letterStack.pop();
            int count = countStack.pop();
            for (int i = 0; i < count; ++i) {
                sb.append(letter);
            }
        }
        sb.reverse();
        return sb.toString();
    }
}

class State {
    String board;
    String hand;
    int step;

    public State(String board, String hand, int step) {
        this.board = board;
        this.hand = hand;
        this.step = step;
    }
}

java 解法, 执行用时: 497 ms, 内存消耗: 60.5 MB, 提交时间: 2023-10-27 00:02:40

class Solution {
    public int findMinStep(String board, String hand) {
        char[] arr = hand.toCharArray();
        Arrays.sort(arr);
        hand = new String(arr);

        // 初始化用队列维护的状态队列：其中的三个元素分别为桌面球状态、手中球状态和回合数
        Queue<State> queue = new ArrayDeque<State>();
        queue.offer(new State(board, hand, 0));

        // 初始化用哈希集合维护的已访问过的状态
        Set<String> visited = new HashSet<String>();
        visited.add(board + " " + hand);

        while (!queue.isEmpty()) {
            State state = queue.poll();
            String curBoard = state.board;
            String curHand = state.hand;
            int step = state.step;
            for (int i = 0; i <= curBoard.length(); ++i) {
                for (int j = 0; j < curHand.length(); ++j) {
                    // 第 1 个剪枝条件: 当前球的颜色和上一个球的颜色相同
                    if (j > 0 && curHand.charAt(j) == curHand.charAt(j - 1)) {
                        continue;
                    }

                    // 第 2 个剪枝条件: 只在连续相同颜色的球的开头位置插入新球
                    if (i > 0 && curBoard.charAt(i - 1) == curHand.charAt(j)) {
                        continue;
                    }

                    // 第 3 个剪枝条件: 只在以下两种情况放置新球
                    boolean choose = false;
                    //  - 第 1 种情况 : 当前球颜色与后面的球的颜色相同
                    if (i < curBoard.length() && curBoard.charAt(i) == curHand.charAt(j)) {
                        choose = true;
                    }
                    //  - 第 2 种情况 : 当前后颜色相同且与当前颜色不同时候放置球
                    if (i > 0 && i < curBoard.length() && curBoard.charAt(i - 1) == curBoard.charAt(i) && curBoard.charAt(i - 1) != curHand.charAt(j)) {
                        choose = true;
                    }

                    if (choose) {
                        String newBoard = clean(curBoard.substring(0, i) + curHand.charAt(j) + curBoard.substring(i));
                        String newHand = curHand.substring(0, j) + curHand.substring(j + 1);
                        if (newBoard.length() == 0) {
                            return step + 1;
                        }
                        String str = newBoard + " " + newHand;
                        if (visited.add(str)) {
                            queue.offer(new State(newBoard, newHand, step + 1));
                        }
                    }
                }
            }
        }
        return -1;
    }

    public String clean(String s) {
        StringBuffer sb = new StringBuffer();
        Deque<Character> letterStack = new ArrayDeque<Character>();
        Deque<Integer> countStack = new ArrayDeque<Integer>();
        
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            while (!letterStack.isEmpty() && c != letterStack.peek() && countStack.peek() >= 3) {
                letterStack.pop();
                countStack.pop();
            }
            if (letterStack.isEmpty() || c != letterStack.peek()) {
                letterStack.push(c);
                countStack.push(1);
            } else {
                countStack.push(countStack.pop() + 1);
            }
        }
        if (!countStack.isEmpty() && countStack.peek() >= 3) {
            letterStack.pop();
            countStack.pop();
        }
        while (!letterStack.isEmpty()) {
            char letter = letterStack.pop();
            int count = countStack.pop();
            for (int i = 0; i < count; ++i) {
                sb.append(letter);
            }
        }
        sb.reverse();
        return sb.toString();
    }
}

class State {
    String board;
    String hand;
    int step;

    public State(String board, String hand, int step) {
        this.board = board;
        this.hand = hand;
        this.step = step;
    }
}

java 解法, 执行用时: 661 ms, 内存消耗: 53.7 MB, 提交时间: 2023-10-27 00:02:17

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 + "_" + (1 << m), 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;
                    String hashKey = nextStr + "_" + next;
                    if (!map.containsKey(hashKey) || map.get(hashKey) > step + 1) {
                        map.put(hashKey, step + 1);
                        q.add(new Node(nextStr, next, f(nextStr, next), step + 1));
                    }
                }
            }
        }
        return -1;
    }
}

java 解法, 执行用时: 435 ms, 内存消耗: 53.2 MB, 提交时间: 2023-10-27 00:02:05

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;
        String hashKey = a + "_" + cur;
        if (map.containsKey(hashKey)) return map.get(hashKey);
        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(hashKey, ans);
        return ans;
    }
}