/*
93. Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
*/
/*
    如果長度為12场靴，只能是3個3個切割

*/

func restoreIpAddresses(_ ipString: String) -> [String] {
    func isValid(_ subIp: String) -> Bool {
        //長度限制
        let length = subIp.lengthOfBytes(using: .ascii)
        guard length <= 3, length > 0 else {
            return false
        }

        //第一個字符為0煤禽，但整體長度>1
        if subIp.characters.first == "0", length > 1 {
            return false
        }

        //數(shù)值超過255
        if let value = Int(subIp) {
            if (value > 255) {
                return false
            }
        } else {
            return false
        }

        return true
    }

    let length = ipString.lengthOfBytes(using: .ascii)
    guard length >= 4 else {
        return []
    }

    var retStringArray: [String] = []

    var startIndex = ipString.startIndex
    var endIndex = ipString.endIndex

    //i,j,k 標(biāo)識每次選擇結(jié)束的 index圣贸，一旦前面的選擇完隔躲，最后一個就可以確定，
    //中途每一次選擇柴灯，如果 index 超過了 length卖漫，則直接退出
    for i in 0 ..< 3 {
        func canDealSection(_ start: Int, _ end: Int) -> (Bool, String) {
            if end >= (length - 1) {
                return (false, "")
            }

            let tldEndIndex = ipString.index(ipString.startIndex, offsetBy: end+1)
            let tldStartIndex = ipString.index(ipString.startIndex, offsetBy: start)
            let range = Range(uncheckedBounds: (lower: tldStartIndex, upper: tldEndIndex))
            let section = ipString.substring(with: range)
            if isValid(section) {
                return (true, section)
            } else {
                return (false, "")
            }
        }
        var section1 = ""
        let (status, value) = canDealSection(0, i)
        if !status {
            break
        }
        section1 = value
        print("section1 is \(section1)")
        for j in i + 1 ..< i + 4 {
            var section2 = ""
            let (status, value) = canDealSection(i+1, j)
            if !status {
                break
            }
            section2 = value
            print("section2 is \(section2)")
            for k in j + 1 ..< j + 4 {
                var section3 = ""
                let (status, value) = canDealSection(j+1, k)
                if !status {
                    break
                }
                section3 = value
                print("section3 is \(section3)")
                //最后一個section费尽，由剩余長度決定
                let index = ipString.index(ipString.startIndex, offsetBy: k + 1)
                let section4 = ipString.substring(from: index)
                print("section4 is \(section4)")
                if isValid(section4) {
                    var validIpString = ""
                    validIpString.append(section1)
                    validIpString.append(".")
                    validIpString.append(section2)
                    validIpString.append(".")
                    validIpString.append(section3)
                    validIpString.append(".")
                    validIpString.append(section4)
                    retStringArray.append(validIpString)
                    print("----- \(validIpString) -----")
                }
            }
        }
    }

    return retStringArray
}