My C++ Solution, 3ms


  • 0
    X

    I think it is easy to understand.

    class Solution {
    public:
        int ans = 0;
        int findMinStep(string board, string hand) {
            ans += hand.size()+1;
            unordered_map<char, int> um;
            for (int i = 0; i < hand.size(); i++) um[hand[i]]++;
            dfs(board, 0, um);
            if (ans == hand.size()+1) return -1;
            return ans;
        }
    
        void dfs(string board, int cnt, unordered_map<char, int>& um) {
            int blen = board.size();
            if (blen == 0) {
                ans = min(ans, cnt);
                return;
            }
            for (int i = 0; i < blen; i++) {
                if (i != blen-1 && board[i] ==  board[i+1] && um[board[i]] >= 1) {
                    string tb = help(board.substr(0, i)+board.substr(i+2));
                    um[board[i]] -= 1;
                    dfs(tb, cnt+1, um);
                    um[board[i]] += 1;
                }
                if (um[board[i]] >= 2) {
                    string tb = help(board.substr(0,i)+board.substr(i+1));
                    um[board[i]] -= 2;
                    dfs(tb, cnt+2, um);
                    um[board[i]] += 2;
                }
            }
        }
    
        string help(string str) {
            if (str.size() < 3) return str;
            int i = 0, j = 1, len = str.size();
            while (j < len) {
                if (str[j] == str[i]) j++;
                else if (j-i >= 3) break;
                else {
                    i = j;
                    j++;
                }
            }
            if (j-i >= 3) return help(str.substr(0,i)+str.substr(j));
            return str;
        }
    };
    

Log in to reply
 

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