93. Restore IP Addresses

[LLancelot]

https://leetcode.com/problems/restore-ip-addresses/

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

A valid IP address consists of exactly four integers (each integer is between 0 and 255) separated by single points.

Example:

Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"]

class Solution(object):
    def restoreIpAddresses(self, s):

        def dfs(res, s, curr, field):
            if field == 4 and s == "":
                res.append(curr[1:])
            elif field == 4 or s == "":
                return 
            else:
                # add 1 digit into curr, then dfs
                dfs(res, s[1:], curr + "." + s[0:1], field + 1)

                # add 2 digits into curr, then dfs
                if s[0] != "0" and len(s) > 1:
                    dfs(res, s[2:], curr + "." + s[0:2], field + 1)

                    # add 3 digits into curr, then dfs
                    if len(s) > 2 and int(s[0:3]) <= 255:
                        dfs(res, s[3:], curr + "." + s[0:3], field + 1)

        res=[]
        if not s or len(s) > 12:
            return res

        dfs(res, s, "", 0)
        return res