class Solution(object): def restoreIpAddresses(self, s): """ :type s: str :rtype: List[str] """ ans =  for i in range(1, len(s)): for j in range(i + 1, i + 4): for k in range(j + 1, j + 4): if k < len(s): ip = [s[:i], s[i:j], s[j:k], s[k:]] # Valid numbers and valid string if (all([0 <= int(x) <= 255 for x in ip]) and all([x == '0' or x != '0' for x in ip])): ans.append('.'.join(ip)) return ans
The program above was accepted by the online judge in 448 ms. It only beats 0.36% Python submissions. I would like to ask for an improvement of this problem.
My algorithm is simply checking every valid location of
i, which is the first '.' of the IP address. I expect the time complexity is O(n).
My implementation might be slow. Instead of using
all, explicitly written down each condition, such as
0 <= int(s[:i]) <= 255 and 0 <= int(s[i:j]) <= 255 and ... makes the program run slightly faster. But the running time was around 140 ms, which is still slow comparing with other Python submissions.
Could anyone share your insight of solving this problem?