**一. 題目描述** 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) **二. 題目分析** 題目的大意是，輸入一個僅含整數的字符串，找出所有合法的ip地址，并輸出所有的可能性。 很顯然這道題需要遍歷到最后一個字符才能判斷一個解是否合法，因此需使用dfs。本題的難點在于存在各種各樣的限制條件，如每段中不能出現以0開頭的數字。需反復嘗試方可AC，由于時間有限，給出一個參考的代碼鏈接，后續需深入研究。 **三. 示例代碼** ~~~ class Solution { public: vector<string> restore(string s, int n, bool &flag) { vector<string> res; if(s.length() < n) {flag = false; return res;} if(n==1) { if(s.length()>3){flag=false;return res;}//maybe larger than int int ip = stoi(s); if(ip==0 && s.length() >1) flag = false; else if(ip>0 && s[0] == '0') flag = false; else if((ip >= 0) && (ip < 256)) { res.push_back(s); flag = true; }else flag = false; return res; } int loop = s.length() - n +1;//garuntee every ip address is no less than one bit loop = min(loop,3); for(int i = 1; i <= loop; i++) { string ipstr = s.substr(0,i); int ip = stoi(ipstr); if(ip==0 && ipstr.length() >1)break; if(ip>0 && ipstr[0] == '0')break; if((ip>=0) && (ip < 256)) { string suffix = s.substr(i); bool f = false; vector<string> tmp = restore(suffix,n-1,f); if(f) { flag = true; for(int k = 0; k < tmp.size(); k++) res.push_back(ipstr + '.' + tmp[k]); } } } return res; } vector<string> restoreIpAddresses(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<string> res; bool flag = false; res = restore(s,4,flag); return res; } } ~~~ **四. 小結** 遞歸到最后一個數并進行判斷，最后輸出結果。