2 different methods in Swift with explanation and examples


  • 0

    The first method is just directly calculating the result using multiplication method.

    For example, string "113". This method uses multiplication to calculate the next num "3", the count of number "3" is 2*2-1 = 3. But here after 4 valid contiguous characters, like "121213", the equation is ((2*2-1)*2-1)*2-2 = 8, we need to minus ex += 1. This is all about mathematics.

    func numDecodings(s: String) -> Int {
        if s.isEmpty || s[s.startIndex] == "0" { return 0 }
        if s.characters.count == 1 { return 1 }
        var i = s.endIndex.predecessor()
        var count = 1
        while i > s.startIndex {
            if s[i] == "0" && s[i.predecessor()] != "2" && s[i.predecessor()] != "1" {
                return 0
            }else if s[i] == "0" && i.predecessor() != s.startIndex {
                i = i.predecessor().predecessor()
            }else if s[i] == "0" && i.predecessor() == s.startIndex {
                return count
            }else if s[i.predecessor()] == "1" || (s[i.predecessor()] == "2" && s[i] <= "6") {
                var tag = 2, ex = 1
                i = i.predecessor()
                print("out:\(tag)")
                while i > s.startIndex && (s[i.predecessor()] == "1" || (s[i.predecessor()] == "2" && s[i] <= "6")) {
                    tag <<= 1
                    tag -= ex
                    if tag >= 5 { ex += 1 }
                    i = i.predecessor()
                    print(":\(tag)")
                }
                count *= tag
            }else {
                i = i.predecessor()
            }
        }
        return count
    }
    

    The second method uses addition method, which is easier to write the code, but for me, it's much harder to think about.

    For example, string "121", it can be decoded as "1, 2,1", "12, 1" and "1, 21", when we add another number, for example "2", we actually add this "2" after "1, 2,1", "12, 1", because "1, 21" has used the last "1" in its "21". In the same way, we add another number "7" after "1212", we actually add this "7" on "1,2,1,2", "12,1,2", "1,21,2", because only these 3 messages have a free last number "2" which can be composed with "7". Well, how many of the free number at every time? This is this question really about.

    func numDecodings(s: String) -> Int {
        if s.isEmpty || s[s.startIndex] == "0" { return 0 }
        if s.characters.count == 1 { return 1 }
        var count = 1, last = 1
        var i = s.startIndex.successor()
        while i < s.endIndex {
            var cur = 0
            if s[i] > "0" {
                cur += count
            }
            if s[i.predecessor()] == "1" || (s[i.predecessor()] == "2" && s[i] <= "6") {
                cur += last
            }
            last = count
            count = cur
            if last == 0 {
                return 0
            }
            i = i.successor()
        }
        return count
    }
    

Log in to reply
 

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