Simple C++ solution


  • 0
    L

    The solution uses DFS search only without preprocessing or memoization.

    int findMinStep(string board, string hand) {
        if (board.length() == 0)
        {
            return 0;
        }
    
        // store all possible insertions
        set<int> insertions;
    
        int seqLen = 0;
        for (size_t i = 0; i < board.length(); ++i)
        {
            ++seqLen;
    
            if (i + 1 == board.length() || board[i] != board[i + 1])
            {
                // At the end of a sequence, DFS search the following:
                if (seqLen >= 3)
                {
                    // 1. There is a long seq (length >= 3), simply remove it and process the new string
                    string _board = board;
                    _board.erase(i + 1 - seqLen, seqLen);
                    int insertion = findMinStep(_board, hand);
                    if (insertion >= 0) insertions.insert(insertion);
                    // Do not continue to the case 3 as it would be duplicate.
                    break;
                }
                else if (hand.find(board[i]) != string::npos)
                {
                    // 2. Insert a char from hand, recursively process the new string.
                    string _board = board, _hand = hand;
                    _board.insert(i, 1, board[i]);
                    _hand.erase(hand.find(board[i]), 1);
                    int insertion = findMinStep(_board, _hand);
                    if (insertion >= 0) insertions.insert(insertion + 1);
                }
    
                // 3. Continue processing the rest of string.
    
                // Reset sequence length counter.
                seqLen = 0;
            }
        }
    
        return insertions.empty() ? -1 : *insertions.begin();      
    }

Log in to reply
 

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