0093. Restore IP Addresses (Medium)
Question
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
| |
分析/解題
給定一個僅含數字0~9的字串，將其還原成所有合法的IP位址的可能組合。
對於IP而言，我們所需考慮的有以下幾個條件：
1. 共分4段(且必須恰好是4段)
2. 中間以小數點連接，每組的數字在0~255之間
如果定義再清楚一點的話，
可以補上前面寫0的部分除了0以外不能納入，會更好一點。
(比如113.002.22.3不會是合法的IP，但一個IP可以是0.0.0.0)
所以這題也是很典型的Backtracking+DFS 的題目：
每次從s上面按順序取一段長度，檢查它是否合法，
再遞迴取下一段。
那麼，我們需要考慮一些邊界的條件，
以便於我們考慮什麼時候該「回頭」：
最基本的條件，就是已經分到第4段 了，
我們應該要考慮這段剩下的部分是否合法。
- 當剩下的長度>3 => 根本就超過了，完全不用考慮XD
- 剩下的長度≤3且轉成數字≤255 ，即可將該段補齊並加到結果。
例外：連續的0會有問題，所以要優先檢查是否剛好為'0’ 的狀況，
除了剛好為"0"的狀況外，首字元為'0’就必須被排除掉 。
邊界條件考慮完後，我們來考慮一般的分段法。
在開始之前，可以先排除掉剩下的長度小於所需的分段數 的狀況，
用以避免取分段時超出邊界。
(例如剩下長度為2，但還需要取3段，那麼顯然不夠用)
假設現在我們接下來要取的位置在 i ，要取 j 個字元：
那麼 j可以是1~3，但 i+j 不能超過s的長度 。
我們會發現額外要考慮的就是上面的2的部分 ，
取完一段以後，呼叫相同的函式進行遞迴，
不要忘記除了上一次傳進來的前導字串cur 外，
要加上的是這次取的分段 ，以及分隔用的小數點"." 。
依此，寫成程式碼如下：
Java
Java的部分，我們使用LinkedList來記錄結果res，
傳入的參數有該字串s，res，當前要取的索引值i，
當前的分段cnt(從0起算)，以及到目前為止的IP的字串cur。
由於每次呼叫checkIP時帶進去的字串都是新生成 的，
所以回到上一層時就自然還原了cur的狀態，
不用像之前的棋盤搜尋字串問題中需要額外考慮要還原的問題。
每次開始前不要忘記檢查s.length()-i < 4 - cnt的邊界 ，
若已經不符則可直接return。
(註：理論上也可以額外檢查s.length()-i > (4-cnt)*4的邊界，
但實測上並不會因此變快，推估可能理由和檢查255的問題一樣)
另外請務必留意在比較字串是否相等時請使用equals()的函式 ，
不要使用"=="(會出錯) 。
Python
Python的部分也是一樣的概念，
只是substring的操作可以簡單用s[i:j] 的形式來處理，
且比較相等可以直接使用"=="。
面試實際可能會遇到的問題
「時間/空間複雜度？」
(O(len(s)) / O(len(s))，更廣義來說，其實長度必須在12 以內，
所以最大的佔用空間和時間是可以固定的 ，
要說O(1)也不太算有錯就是了。)
「為什麼不是當3位數才檢查小於等於255？」
(這樣必須要先分開3位數及其他，變成要先經過另一組判斷式，
整體而言不會比較節省時間。)
相似及延伸
Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)
從LeetCode學演算法，我們下次見囉，掰~
感謝大家對這系列文章的支持！這邊跟大家自我工商一下：
筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VEQZV7E**