A Python solution beats 0.36% submission, ask for improvement.


  • 0
    C
    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] != '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?


Log in to reply
 

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