0093.Restore IP Addresses

Link: 93. Restore IP Addresses - Medium

Question

Restate the problem

Given s, contains only digit
Return possible IP address
Process: segment IP address, between 0 and 255, no leading 0

---

Method 1 Pointer: not apply, Because pointer keep moving, hard to tell which cuts can be valid.
Method 2 Backtracking. Choose a segment length

Method - Backtracking

Approach

• dfs(idx, path)
• Base case:
  • if idx > n, return
  • if idx == n and len(path) == 4, append, return
• Try segment length(1, 2, 3)
  • next_idx = idx + length
  • segment = s[idx: next_idx]
  • if is_valid(segment): choose it and recurse backtrack(next_idx, segment + [segment])

Complexity

• Time Complexity: O($3^4$) constant time
• Space Complexity: O(1)

Edge Case

• [0, 0, 0, 0]

Code

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        address = []
        n = len(s)
        def dfs(idx, path):
            if len(path) > 4:
                return
 
            if idx == n and len(path) == 4:
                address.append(".".join(path))
                return
 
            for length in (1, 2, 3):
                part = s[idx: idx + length]
                if idx + length > n:
                    break
 
                if part[0] == "0" and len(part) > 1:
                    continue 
                
                if int(part) > 255:
                    continue
 
                path.append(s[idx: idx + length])
                dfs(idx + length, path)
                path.pop()
        
        dfs(0, [])
        return address

---

History

Jan-24-2026 Peeked

• did not add enough cut branch
• if idx = n, means correct answer

Jan-21-2026 Hinted

• Spent a long time on deciding correct algorithm
• Got stuck on Boundary, end better to set as the next start