Leetcode 93. Restore IP Addresses

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

IP address should be 4 parts, each part can be at most 3 digits and cannot exceed 255. Also '0' is allowed while '00' is illegal. DFS is a good way.

Solution:

# T:O(3^4) S:O(3*4)
class Solution:
    # @param s, a string
    # @return a list of strings
    def restoreIpAddresses(self, s):
        def dfs(s, sub, ips, ip):
            if sub == 4:                                        
            # when 4 parts, done
                if s == '':
                    ips.append(ip[1:])                          
                    # remove first '.'
                return
            for i in range(1, 4):
                if i <= len(s):
                    if int(s[:i]) <= 255:
                        dfs(s[i:], sub+1, ips, ip+'.'+s[:i])
                    if s[0] == '0': break
                    # when s starts with 0, get it and break
        dfs(s, 0, ips, '')
        return ips

Run Time: 68 ms