跳到主要内容

93. 复原IP地址(Medium)

题目​

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

样例​

Input：s = "25525511135"
Output：["255.255.11.135","255.255.111.35"]

题目解析​

todo...

Python示例​

def backtracking(s, startIndex, ans, tmp):
    if len(tmp) == 3: # 分割三次
        if isValid(s[startIndex:]):
            ans.append('.'.join(tmp) + '.' + s[startIndex:])
        return 

    for i in range(startIndex, startIndex + 3):
        if isValid(s[startIndex: i + 1]):
            tmp.append(s[startIndex: i + 1])
            backtracking(s, i + 1, ans, tmp)
            tmp.pop()
    
def isValid(s):
    """ 
      判断是否合法
    """
    if not s: return False # 1. 非空
    if s[0] == '0' and len(s) > 1: return False  # 2. 不能有前导零： 01 010 
    if int(s) > 255: return False   # 3. 0 ~ 255 范围
    return True 

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        ans = []
        backtracking(s, 0, ans, [])
        return ans