本文主要是介绍[LeetCode]93.Restore IP Addresses,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!