題目
給定一個只包含數字的字符串，復原它并返回所有可能的 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 地址。
思考
這一題和leetcode 131. 分割回文串 思考分析很像，都屬于利用回溯法分割字符串，所以解法上具有一定相似性。
回溯終止條件
如果逗號已經插入了3次了，觀察最后一次插入往后的位置，觀察剩下來的字符串能否構成合法字符串。
如果能構成，那么將s裝入結果；
如果不能構成，回溯到上一個階段。
//如果逗號數量為3，判斷第四個子區間是否合法，如果合法就放入結果中
if(point_nums==3)
{if(isValid(s,startindex,s.size()-1)){result.push_back(s);}return;
}
回溯邏輯
1、這里利用逗號來進行分割，在原string上進行操作。如果startindex~i之間的字符串合法的話，我們就在i后面插入一個逗號。
然后對逗號后面的字符串進行回溯遍歷。不滿足的回溯組合將把逗號消除，完成回撤。
for(int i=startindex;i<s.size();i++)
{//子串區間：[startindex,i]if(isValid(s,startindex,i)) //判斷子串區間的子串是否合法{s.insert(s.begin()+i+1,'.'); //在i后面插入一個逗號point_nums++;backtracking(s,i+2); //切割過的字符不能再次被切割，插入逗號之后下一個子串的起始位置發生往后移動1//回溯撤銷point_nums--;s.erase(s.begin()+i+1); //回溯刪除逗號}//不合法的子串直接結束本層循環，只要一個子串不合法，結果就是不合法的else break;
}
2、考察字符串是否合法：
//判斷字符串s[start,end]組成的數字是否合法
bool isValid(const string& s,int start,int end)
{if(start>end) return false;if(s[start]=='0' && start!=end) //0開頭的數字不合法{return false;}int num=0;for(int i=start;i<=end;i++){if(s[i]>'9' ||s[i]<'0')//遇到非數字字符不合法{return false;}num =num*10+(s[i]-'0');if(num>255) return false;}return true;
}
完整代碼
class Solution {
public:vector<string> result;int point_nums=0;//判斷字符串s[start,end]組成的數字是否合法bool isValid(const string& s,int start,int end){if(start>end) return false;if(s[start]=='0' && start!=end) //0開頭的數字不合法{return false;}int num=0;for(int i=start;i<=end;i++){if(s[i]>'9' ||s[i]<'0')//遇到非數字字符不合法{return false;}num =num*10+(s[i]-'0');if(num>255) return false;}return true;}//這里直接對s進行修改void backtracking(string& s,int startindex){//如果逗號數量為3，判斷第四個子區間是否合法，如果合法就放入結果中if(point_nums==3){if(isValid(s,startindex,s.size()-1)){result.push_back(s);}return;}for(int i=startindex;i<s.size();i++){//子串區間：[startindex,i]if(isValid(s,startindex,i)) //判斷子串區間的子串是否合法{s.insert(s.begin()+i+1,'.'); //在i后面插入一個逗號point_nums++;backtracking(s,i+2); //切割過的字符不能再次被切割，插入逗號之后下一個子串的起始位置發生往后移動1//回溯撤銷point_nums--;s.erase(s.begin()+i+1); //回溯刪除逗號}//不合法的子串直接結束本層循環，只要一個子串不合法，結果就是不合法的else break;}}vector<string> restoreIpAddresses(string s) {result.clear();point_nums=0;backtracking(s,0);return result;}
};
)
