題目

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地址的一項，然后遞歸處理剩下的項。可以想象出一顆樹，每個結點有三個可能的分支（因為范圍是0-255，所以可以由一位兩位或者三位組成），每個數都必須小于等于255。并且這里樹的層數不會超過四層，因為IP地址由四段組成，到了之后我們就沒必要再遞歸下去，可以結束了。

代碼

/*--------------------------------------- * 日期：2015-05-15 * 作者：SJF0115 * 題目: 93.Restore IP Addresses * 網址：https://leetcode.com/problems/restore-ip-addresses/ * 結果：AC * 來源：LeetCode * 博客： -----------------------------------------*/ #include <iostream> #include <vector> using namespace std;class Solution { public:vector<string> restoreIpAddresses(string s) {vector<string> result;int size = s.size();if(size == 0){return result;}//ifstring ip;helper(s,1,0,ip,result);return result;} private:int to_int(string str){int size = str.size();if(size == 0){return 0;}//ifint result = 0;for(int i = 0;i < size;++i){result = result * 10 + str[i] - '0';}//forreturn result;}void helper(string &str,int step,int index,string ip,vector<string> &result){// 終止條件int size = str.size();if(step == 5){if(index == size){result.push_back(ip);}//ifreturn;}//ifstring part;for(int i = 1;i <= 3;++i){// 不能以0開始(單個0可以)if(i != 1 && str[index] == '0'){break;}//ifif(index+i <= size){part = str.substr(index,i);if(to_int(part) <= 255){string tmp = ip;if(step != 1){tmp += ".";}//iftmp += part;helper(str,step+1,index+i,tmp,result);}//if}//if}//for} };int main(){Solution s;//string str("25525511135");string str("010010");vector<string> vec = s.restoreIpAddresses(str);for(int i = 0;i < vec.size();++i){cout<<vec[i]<<endl;}//forreturn 0; }

運行時間

總結

以上是生活随笔為你收集整理的[LeetCode]93.Restore IP Addresses的全部內容，希望文章能夠幫你解決所遇到的問題。

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