思路

意識(shí)到這是切割問(wèn)題，「切割問(wèn)題就可以使用回溯搜索法把所有可能性搜出來(lái)」

回溯三部曲

遞歸參數(shù)
在回溯算法：分割回文串中我們就提到切割問(wèn)題類似組合問(wèn)題。

startIndex一定是需要的，因?yàn)椴荒苤貜?fù)分割，記錄下一層遞歸分割的起始位置。

本題我們還需要一個(gè)變量pointNum，記錄添加逗點(diǎn)的數(shù)量。

遞歸終止條件
終止條件和回溯算法：分割回文串情況就不同了，本題明確要求只會(huì)分成4段，所以不能用切割線切到最后作為終止條件，而是分割的段數(shù)作為終止條件。

pointNum表示逗點(diǎn)數(shù)量，pointNum為3說(shuō)明字符串分成了4段了。
然后驗(yàn)證一下第四段是否合法，如果合法就加入到結(jié)果集里

單層搜索的邏輯

在回溯算法：分割回文串中已經(jīng)講過(guò)在循環(huán)遍歷中如何截取子串。

在for (int i = startIndex; i < s.size(); i++)循環(huán)中 [startIndex, i]這個(gè)區(qū)間就是截取的子串，需要判斷這個(gè)子串是否合法。

如果合法就在字符串后面加上符號(hào).表示已經(jīng)分割。

如果不合法就結(jié)束本層循環(huán)，如圖中剪掉的分支：

然后就是遞歸和回溯的過(guò)程：

遞歸調(diào)用時(shí)，下一層遞歸的startIndex要從i+2開(kāi)始（因?yàn)樾枰谧址屑尤肓朔指舴?），同時(shí)記錄分割符的數(shù)量pointNum 要 +1。

回溯的時(shí)候，就將剛剛加入的分隔符. 刪掉就可以了，pointNum也要-1。

判斷子串是否合法

考慮以下三點(diǎn)：
1、段位以0為開(kāi)頭的數(shù)字不合法
2、段位里有非正整數(shù)字符不合法
3、段位如果大于255了不合法

class Solution { private:vector<string> result;// 記錄結(jié)果// startIndex: 搜索的起始位置，pointNum:添加逗點(diǎn)的數(shù)量void backtracking(string& s, int startIndex, int pointNum) {if (pointNum == 3) { // 逗點(diǎn)數(shù)量為3時(shí)，分隔結(jié)束// 判斷第四段子字符串是否合法，如果合法就放進(jìn)result中if (isValid(s, startIndex, s.size() - 1)) {result.push_back(s);}return;}for (int i = startIndex; i < s.size(); i++) {if (isValid(s, startIndex, i)) { // 判斷 [startIndex,i] 這個(gè)區(qū)間的子串是否合法s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一個(gè)逗點(diǎn)pointNum++;backtracking(s, i + 2, pointNum); // 插入逗點(diǎn)之后下一個(gè)子串的起始位置為i+2pointNum--; // 回溯s.erase(s.begin() + i + 1); // 回溯刪掉逗點(diǎn)} else break; // 不合法，直接結(jié)束本層循環(huán)}}// 判斷字符串s在左閉又閉區(qū)間[start, end]所組成的數(shù)字是否合法bool isValid(const string& s, int start, int end) {if (start > end) {return false;}if (s[start] == '0' && start != end) { // 0開(kāi)頭的數(shù)字不合法return false;}int num = 0;for (int i = start; i <= end; i++) {if (s[i] > '9' || s[i] < '0') { // 遇到非數(shù)字字符不合法return false;}//計(jì)算字符串組成的數(shù)字大小，如"255"組成的數(shù)字大小num = num * 10 + (s[i] - '0');if (num > 255) { // 如果大于255了不合法return false;}}return true;} public:vector<string> restoreIpAddresses(string s) {result.clear();backtracking(s, 0, 0);return result;} };

總結(jié)

以上是生活随笔為你收集整理的复原ip地址的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。