# 100 lines solution

• #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;
}
};

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