[LeetCode] 93. Restore IP Addresses

轉自LeetCode

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

<Solution>

這題是要將字串組合成合法的 ip address

雖然字串問題通常會先想到 dp，但是這題是在求所有可能的組合

這時候反而是要用 DFS 的想法

解題想法如下（參考資料）

• 將 s 分成四段，每段的長度是 1 到 3，並用遞迴處理每一段

• 每一段都要檢查是否合法，數值範圍要在 0 - 255，且不能有 010，011這種情況出現

• 當四段都處理完後，還要確保 s 裡面的字元都有用到，不然就代表 s 包含過多字元

code 如下

還有更精簡的寫法，可以把 isValid() 拿掉

• 當遞迴的過程中，s 的長度不足 1 的時候，就直接結束

• i == to_string(num).length()，這個是用來濾掉 "010"，"011" 這種字串

舉例 : "010"，當 int num = stoi("010")，num = 10，這時候 i = 3，因為當下處理的字串長度是 3
然後使用 to_string(num) 會得到 "10"，這時候長度反而變 2，因為前綴的0被拿掉了
所以可以使用 i == to_string(num).length() 來過濾有前綴無意義 0 的字串

code 如下

那因為這題的情況不會很多，IP 固定會有四段，每段長度 1 到 3

所以就用暴力法，四個 for 迴圈下去組合

然後也運用上面提到的 stoi 之後的數字，再用 to_string 轉回字串，其長度可以用來濾掉 "010" 這種情況的方式

code 如下