100 lines solution


  • 0
    H
    #define INF 999999
    #define mem(a,v) memset(a,v,sizeof(a))
    #define maxn 55
    
    
    class Solution {
    public:
        string insertHand(string board,int k,char h){
            string ans;
            if(k<board.length()-1)
                ans = board.substr(0,k+1)+h+board.substr(k+1,board.length()-1-k);
            else
                ans = board+h;
            return ans;
        }
        string removeThree(string board,int k,int count){
            string ans;
            if(k<board.length()-1 && k-count+1>0)
                ans = board.substr(0,k-count+1)+board.substr(k+1,board.length()-1-k);
            else if(k<board.length()-1)
                ans = board.substr(k+1,board.length()-1-k);
            else if(k-count+1>0)
                ans = board.substr(0,k-count+1);
            else
                ans = "";
            return ans;
    
        }
        int work(string board, string hand){
            if(hand.length()==0)
            {
                if(board.length())
                    return INF;
                else
                    return 0;
            }
            char now = hand[0];
            hand = hand.substr(1,hand.length()-1);
            if(board.length()==0)
                return 0;
            int ans = INF;
            for(int i=1;i<board.size();i++)
            {
                if(board[i]!=board[i-1])
                {
                    if(board[i-1]==now)
                    {
                        string newBoard = insertHand(board,i-1,now);
                        int flag = 1;
                        while(flag)
                        {
                            flag = 0;
                            int count = 1;
                            for(int j=1;j<newBoard.length();j++)
                            {
                                if(newBoard[j]==newBoard[j-1])
                                    count++;
                                else
                                {
                                    if(count>=3)
                                    {
                                        newBoard = removeThree(newBoard,j-1,count);
                                        flag = 1;
                                        break;
                                    }
                                    count = 1;
                                }
                            }
                            if(!flag)
                                if(count>=3)
                                {
                                    newBoard = removeThree(newBoard,newBoard.length()-1,count);
                                }
                        }
                        ans = min(ans,work(newBoard,hand)+1);
                    }
                }
            }
            if(board[board.length()-1]==now){
                string newBoard = insertHand(board,board.length()-1,now);
                int flag = 1;
                while(flag)
                {
                    flag = 0;
                    int count = 1;
                    for(int j=1;j<newBoard.length();j++)
                    {
                        if(newBoard[j]==newBoard[j-1])
                            count++;
                        else
                        {
                            if(count>=3)
                            {
                                newBoard = removeThree(newBoard,j-1,count);
                                flag = 1;
                                break;
                            }
                            count = 1;
                        }
                    }
                    if(!flag)
                        if(count>=3)
                        {
                            newBoard = removeThree(newBoard,newBoard.length()-1,count);
                        }
                }
                ans = min(ans,work(newBoard,hand)+1);
            }
            ans = min(ans,work(board,hand));
            return ans;
        }
        void getAll(string hand,int now,vector<string> &store){
            if(now==hand.length())
                store.push_back(hand);
            for(int i=now;i<hand.length();i++)
            {
                swap(hand[now],hand[i]);
                getAll(hand,now+1,store);
            }
        }
        int findMinStep(string board, string hand) {
            int ans = INF;
            vector<string> store;
            getAll(hand,0,store);
            for(int i=0;i<store.size();i++)
                ans = min(ans,work(board,store[i]));
            if(ans<INF)
                return ans;
            else
                return -1;
        }
    };
    

Log in to reply
 

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