#
# @lc app=leetcode id=93 lang=python3
#
# [93] Restore IP Addresses
#
# https://leetcode.com/problems/restore-ip-addresses/description/
#
# algorithms
# Medium (47.09%)
# Likes:    4571
# Dislikes: 742
# Total Accepted:    392.7K
# Total Submissions: 831.8K
# Testcase Example:  '"25525511135"'
#
# A valid IP address consists of exactly four integers separated by single
# dots. Each integer is between 0 and 255 (inclusive) and cannot have leading
# zeros.
#
#
# For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but
# "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP
# addresses.
#
#
# Given a string s containing only digits, return all possible valid IP
# addresses that can be formed by inserting dots into s. You are not allowed to
# reorder or remove any digits in s. You may return the valid IP addresses in
# any order.
#
#
# Example 1:
#
#
# Input: s = "25525511135"
# Output: ["255.255.11.135","255.255.111.35"]
#
#
# Example 2:
#
#
# Input: s = "0000"
# Output: ["0.0.0.0"]
#
#
# Example 3:
#
#
# Input: s = "101023"
# Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
#
#
#
# Constraints:
#
#
# 1 <= s.length <= 20
# s consists of digits only.
#
#
#
from typing import List


# @lc code=start
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []
        path = []

        def backtracking(index=0):
            if index == len(s):
                if len(path) == 4:
                    res.append(".".join(path))
                return
            if s[index] == "0":
                path.append(s[index])
                backtracking(index + 1)
                path.pop()
            else:
                for i in range(index, len(s)):
                    if 0 <= int(s[index : i + 1]) <= 255:
                        path.append(s[index : i + 1])
                        backtracking(i + 1)
                        path.pop()

        backtracking()
        return res


# @lc code=end
