Swift solution - Backtracking


  • 0
    class Solution {
        func restoreIpAddresses(_ s: String) -> [String] {
            if s.characters.count < 4 || s.characters.count > 12 {
                return []
            }
            
            let characters = Array(s.characters)
            var result = [String]()
            var candidate = [String]()
            
            backtracking(characters, 0, &candidate, &result)
            
            return result
        }
        
        private func backtracking(_ characters: [Character], _ pos: Int, _ candidate: inout [String], _ result: inout [String]) {
            if candidate.count == 4 {
                result.append(candidate.joined(separator: "."))
                return
            }
            
            let charsLeft = characters.count - pos
            let groupsLeft = 4 - candidate.count
            let minLen = groupsLeft == 1 ? charsLeft - groupsLeft + 1 : 1
            let maxLen = characters[pos] == "0" ? 1 : min(3, charsLeft - groupsLeft + 1)
            
            if minLen > maxLen {
                return
            }
    
            for len in minLen...maxLen {
                let num = String(characters[pos..<(pos + len)])
                if Int(num)! > 255 {
                    continue
                }
                candidate.append(num)
                backtracking(characters, pos + len, &candidate, &result)
                candidate.removeLast()
            }
        }
    }
    

Log in to reply
 

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