Question: https://oj.leetcode.com/problems/restore-ip-addresses/
Question Name: Restore IP Addresses
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | class Solution: # @param s, a string # @return a boolean to indicate whether s is a valid IP address section. def restoreIpAddressesHelper(self,s): assert 0 < len(s) <= 3 if len(s) == 1: return True elif len(s) == 2 and s[0] != "0": return True else: if s[0] == "1": return True elif s[0] == "2": if s[1] in "01234": return True elif s[1] == "5": if s[2] in "012345": return True return False # @param s, a string # @return a list of strings def restoreIpAddresses(self, s): # Check the length of s. Too long or too short makes it impossible # to be a valid IP address. if not 4 <= len(s) <= 12: return [] result = [] for i in xrange(1, len(s)-2): # The first section cannot be longer than 3. if i > 3: break for j in xrange(i+1, len(s)-1): # THe second section cannot be longer than 3. if j - i > 3: break for k in xrange(j+1, len(s)): # The third section cannot be longer than 3. if k - j > 3: break # The last section cannot be longer than 3. if len(s) - k > 3: continue # Validate the four sections one by one. if not self.restoreIpAddressesHelper(s[:i]): continue if not self.restoreIpAddressesHelper(s[i:j]): continue if not self.restoreIpAddressesHelper(s[j:k]): continue if not self.restoreIpAddressesHelper(s[k:]): continue # All sections passed the validation. This is a valid # IP address. result.append(s[:i] + "." + s[i:j] + "." + s[j:k] + "." + s[k:]) return result |