Simplest Method


  • 1
    S
    class Solution {
    public:
        void reduce(string &s) { // cancel continuous chars with nums >= 3
            int i = 0, j = 0;
            int n = s.size();
            while (i < n - 2) {
                int j = i;
                while (j < n && s[i] == s[j]) j++;
                if (j-i >= 3) {
                    s.erase(i, j-i);
                    n = s.size();
                    i -= 2;
                    if (i < 0) i = 0;
                } else {
                    i = j;
                }
            }
        }
        
        int findMinStep(string board, string hand) {
            int minCnt = INT_MAX;
            unordered_set<char> usedHand; 
            for (int i = 0; i < hand.size(); i++) {//for each char in hand
                if (usedHand.count(hand[i])) continue; // if we have tested this char before, skip
                usedHand.insert(hand[i]);
                for (int j = 0; j < board.size(); j++) { // for each char in board
                    if (hand[i] != board[j]) continue; // the main idea is insert a char from hand next to the same char in board
                    string s1 = board;
                    string h1 = hand;
                    s1.insert(j, 1, hand[i]);
                    reduce(s1);
                    if (s1.size() == 0) return 1;
                    h1.erase(i, 1);
                    int subCnt = findMinStep(s1, h1); // a new state
                    if (subCnt == -1) continue;
                    minCnt = min(subCnt + 1, minCnt);
                }       
            }
            return minCnt == INT_MAX ?-1 :minCnt;
        }
    };
    

  • 0
    C

    Can you explain your code a little more? What's the time complexity? Thanks


  • 0
    S

    Basically using dfs to test every possible insertion.
    But we only insert a char that from hand next to the same char in board.
    For example, given a char from hand, if it's never appeared in board, then we don't have to process this char; If it appears in board, there are two options, 1) insert it so that it's left or right or both sides have the same chars; 2) insert it so that it's isolated by other different chars.

    It's no doubt that 2) will increase the operations. So every time when insertion happens, insert it next to the same chars, then we try to cancel chars by the rules of ZUMA.

    I thinks the time complexity is based on depth of DFS and length of hand and board.
    If length of board is m, length of hand is n, it's O(m!n!)


Log in to reply
 

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