。･∀･)ﾉ゛
嗨，我是wec，今天是DAY 27。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

給定一個只包含數字的字符串，請將其還原為所有可能的有效的 IP 地址並返回這些地址。
有效的 IP 地址由四個整數（0 到 255）組成，且每個整數用點（.）分隔。整數不能以零開頭，除非它是 0 本身。例如，“0.0.0.0”和“192.168.1.1”是有效的 IP 地址，而“256.256.256.256”、“192.168.01.1”和“192.168.1.256”則是無效的。

🔎 解題思路＆程式碼

1️⃣ 回溯法

第1步： 創建一個空的result列表來儲存有效的 IP 地址。
第2步： 定義回溯函數backtrack與四個參數：
s：原始字符串。
start：當前的起始位置。
path：當前的 IP 地址部分。
result：結果列表。
第3步： 當path的長度為4且start等於字符串長度時，將當前的 IP 地址加入結果。
第4步： 使用一個循環從1到3，遍歷可能的 IP 地址部分長度。根據當前的start位置和length來提取當前部part。檢查part是否有效，若無效則跳過。
第5步： 將有效的part加入path，然後遞歸調用backtrack函數，在回溯時，撤回當前選擇。
第6步： 定義valid_part函數檢查一個部分是否有效，包括長度限制和數值範圍。
程式碼：

def restore_ip_addresses(s)
  result = []
  backtrack(s, 0, [], result)
  result
end

def backtrack(s, start, path, result)
  if path.length == 4 && start == s.length
    result << path.join(".") 
    return
  end

  (1..3).each do |length|
    break if start + length > s.length 

    part = s[start, length]
    next if !valid_part(part) 
    path << part 
    backtrack(s, start + length, path, result)
    path.pop
  end
end

def valid_part(part)
  return false if part.length > 3 || part.length == 0
  return part.to_i <= 255 && (part.length == 1 || part[0] != '0') 
end

🔎 總結

時間複雜度

回溯法： O(1)
➡️ 因為總共會有225種組合，所以主要的解決方法就是利用回溯逐一嘗試的特性將IP恢復成有效的狀態。算是蠻直觀的可以想到要用回溯法解的一道題目☆-(･ε･ !

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃剉冰(珍珠芋圓跟花豆)。
明天要說：Ruby精選刷題！Medium路跑D-20(>∀･)⌒☆