###### tags: `LeetCode` `Medium` `DFS` `String`
# LeetCode #93 [Restore IP Addresses](https://leetcode.com/problems/restore-ip-addresses/)
### (Medium)

給定一個只包含數字的字符串，用以表示一個 IP 地址，返回所有可能從 s 獲得的 有效 IP 地址 。你可以按任何順序返回答案。

有效 IP 地址 正好由四個整數（每個整數位於 0 到 255 之間組成，且不能含有前導 0），整數之間用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 無效 IP 地址。

---
由於IPv4地址每格為0~255, 也就是1~3位數, 因此需分別考慮每位數並呼叫遞迴。

首先, 若給定字串長度小於4(4個1)或大於12(4個3)則直接返回空集合。使用計數器統計目前已完成幾個ip字節(總共4個), 當ip字節數等於4, 且ip位置等於原自串長度+3(新增3個'.')則將該ip加到答案數組中(合法ip)。

要注意的點:
1. substr的使用:與java的substring不同, C++的參數為 目標字串.substr(起始位置, 要從起始位置開始切割多少長度), 也就是說s.substr(4,2)代表從第4個字元開始往後數兩個, 也就是s[5], s[6]這兩個字元。而java的substring則是 目標字串.substring(起始位置, 終止位置)。
2. 若切割出來的ip字節長度大於1, 則不能為0開頭, 比如說: 012、01...等是非法的ip字節。
3. 當處理到第四個字節時不需要再加'.', 所以要一個額外判斷式負責決定。

---

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ans;
        if(s.size()>12||s.size()<4)return {};
        dfs(0, s, 0, "", ans);
        return ans;
    }
    void dfs(int index, const string& s, int times, string tmp, vector<string>& ans){
        if(times==4){
            if(tmp.length()==s.length()+3)
                ans.push_back(tmp);
            return;
        }
        for(int i=1;i<=3;i++){
            if(index+i>s.size())break;
            string subs = s.substr(index, i);
            if(subs.length()>1&&subs[0]=='0')continue;
            if(stoi(subs)<=255)
                dfs(index+i, s, times+1, tmp+subs+(times==3?"":"."), ans);
        }
    }
};