給定一個只包含數字的字符串，用以表示一個 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 地址。

示例 1：
輸入：s = “25525511135”
輸出：[“255.255.11.135”,“255.255.111.35”]

示例 2：
輸入：s = “0000”
輸出：[“0.0.0.0”]

示例 3：
輸入：s = “1111”
輸出：[“1.1.1.1”]

示例 4：
輸入：s = “010010”
輸出：[“0.10.0.10”,“0.100.1.0”]

示例 5：
輸入：s = “101023”
輸出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

提示：

0 <= s.length <= 3000
s 僅由數字組成

這道題依舊是字符串的分割類問題，比上一道131.分割回文串稍微難一點點，但是掌握了基本套路，其他的都是一些小變化；

這道題需要注意的地方只有一個，就是當遞歸進行下一層遍歷時 i 需要加2而不是加 1 ，因為遞歸前已經把字符 ‘.’ 加到了 i + 1的位置了，所以i + 2才是s的下一個字符，
代碼已經把詳細注釋寫上了，解析就不啰嗦了

代碼如下：

class Solution { private:vector<string> ans;//start為搜索起始位置，pointCount為所加字符'.'的個數//回溯函數void backtacking(string& s, int start, int pointCount) {//終止條件為：當所加'.'數為三時正好分為了四個整數if (pointCount == 3) {//判斷該字符串第四個整數是否合法，合法即為一種答案if (isValid(s, start, s.size() - 1)) {ans.push_back(s);}return ;}//橫向遍歷每一個數字的每種情況，start為了在縱向遞歸時不重復使用for (int i = start; i < s.size(); ++i) {//判斷[start, i]區間內的字符是否合法，合法即可進行回溯和遞歸操作if (isValid(s, start, i)) {pointCount++;//在i + 1處插入字符'.'s.insert(s.begin() + i + 1, '.');//因為插入了'.'，所以下一個數字字符在i + 2處backtacking(s, i + 2, pointCount);pointCount--;s.erase(s.begin() + i + 1);}//不合法直接結束該層循環，因為一個不合法整個IP地址都不合法else {break;}}}//判斷字符串s在區間[start, end]所組成的數字是否合法bool isValid(const string& s, int start, int end) {if (start > end) {return false;}//以0開頭的數字不合法if(s[start] == '0' && start != end) {return false;}//大于255的數字不合法int num = 0;for (int i = start; i <= end; ++i) {num = num * 10 + (s[i] - '0');if (num > 255) {return false;}}return true;} public:vector<string> restoreIpAddresses(string s) {backtacking(s, 0, 0);return ans;} };

總結

以上是生活随笔為你收集整理的93. 复原 IP 地址（回溯算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。