golang 刷leetcode：祖玛游戏

const MAXSCORE=6
func findMinStep(board string, hand string) int {
    m:=make(map[string]int)
    if backtrack(board, hand,m) == MAXSCORE{
         return -1
    }
    return m[board+ "," + hand]
}


func backtrack(board,hand string,m map[string]int)int{
    //完成条件
    if len(recur(board))==0{
        return 0
    }
    //中断条件
    score := MAXSCORE
    status := board + "," + hand
    if v,ok:=m[status];ok{
        return v
    } 
        //for循环
            //选择
//                递归消除
            //回溯
            //撤销选择
        for i := 0; i < len(hand); i++ {
            for j := 0; j < len(board); j++ {
                board=board[:j]+string([]byte{hand[i]})+board[j:]
                
                boardNew:=recur(board)
                if len(boardNew)==0{
                   m[status]=1
               
                  if j==len(board)-1{
                        board=board[:j]
                    }else{
                        board=board[:j]+board[j+1:]
                   }  
                   return 1
                }
                
                if i==len(hand)-1{
                     hand=hand[:i]
                }else{
                     hand=hand[:i]+hand[i+1:]
                }


                score = min(score, backtrack(boardNew,hand,m) + 1)
               
               //恢复
                hand=hand[:i]+string([]byte{board[j]})+hand[i:]
                if j==len(board)-1{
                     board=board[:j]
                }else{
                     board=board[:j]+board[j+1:]
                }
            }
        }
        //记忆化保存
      m[status]=score
    return score
}


func min(a, b int)int{
    if a<b{
        return a
    }
    return b
}


//递归消除
func recur(board string)string{
    i:=0
    j:=0
    for ;j<=len(board);j++{
        if j<len(board) &&board[i]==board[j]{
            continue
        }
        if j-i>2{
           return recur(board[0:i]+ board[j:])
        }
        i=j
    }
    return board
}