93. Restore IP Addresses
給你一串數字組成的字串，要你輸出它可能是那些 IP
IP的規則: 共四個 0~255 的數字，中間以 '.' 隔開
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"]
思路:
1.和昨天很像的 DFS，往後嘗試切長度為 1~3 的字串(因為最高是 255)
然後檢查它有沒有在 0~255 內 有的話就塞進參數的 array 裡往下傳
碰到結尾時數字剛好有四個就成功 否則失敗
碰到 0 時可以直接切 因為非零數字不能以 0 開頭所以他只能是 0
Python code:
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
n = len(s)
res = []
def dfs(idx, arr, length):
if length == 4 and idx == n:
res.append('.'.join(arr))
if length == 4 or idx == n:
return
if s[idx] == '0':
dfs(idx+1, arr+['0'], length+1)
else:
for i in range(idx+1, min(idx+3, n)+1):
num = s[idx:i]
if int(num) <= 255:
dfs(i, arr+[num], length+1)
dfs(0, [], 0)
return res
刷題幫DC: https://discord.gg/8Gqm9Z2t