ac solution code


  • 0

    Solution1. In-place Backtracking - time = O(n); space = O(n)

    The basic idea is:

    1. Try to replace all satisfied "++" with "--"
    2. Backtrack/recover and keep going till end of string

    Game:
    "++" => "--": ONLY TWO consecutive "++" can be fliped to "--"

    func generatePossibleNextMoves(_ s: String) -> [String] {
        guard s.count > 0 else {return []}
        var res = [String]()
        var chs = [Character](s.characters)
        
        for i in 0..<chs.count - 1 {
            if chs[i] == chs[i+1] && chs[i] == "+" {// 1. two consecutive "+": "++"
                (i...i+1).forEach {chs[$0] = "-"}   // 2. flip these two "++" to "--"
                res.append(String(chs))
                (i...i+1).forEach {chs[$0] = "+"}   // 3. Backtrack: recover these two "--" to "++"
                
            }
        }
        return res
    }
    

Log in to reply
 

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