Return to Revisions

from typing import List

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        n = len(s)
        res = []
        
        def isValid(segment: str) -> bool:
            return int(segment) < 256 and str(int(segment)) == segment
        
        def backtrack(start: int, path: list):
            if len(path) == 4:
                if start == n:
                    res.append(".".join(path))
                return
            
            for end in range(start + 1, min(start + 4, n + 1)):
                segment = s[start:end]
                if isValid(segment):
                    backtrack(end, path + [segment])  
        
        backtrack(0, [])
        return res

With these changes, I:

• Construct only one segment per recursion call
• Backtrack instead of iterating over every single possibility
• Optimize some string operations.

In theory this should reduce memory, but please update me with results.