[LeetCode] Restore IP Addresses

发布时间:2017-1-21 2:01:39 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"[LeetCode] Restore IP Addresses",主要涉及到[LeetCode] Restore IP Addresses方面的内容,对于[LeetCode] Restore IP Addresses感兴趣的同学可以参考一下。

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) #define pb push_back #define pp pop_back class Solution { public: vector<string> restoreIpAddresses(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<string> ret; string cur; solve(s,0,1,cur,ret); return ret; } void solve(string& s,int i,int kth,string& cur,vector<string>& ret) { int len=s.length(); if ( i>=len || kth>4 ) { if ( i==len && kth==5) ret.pb(cur); return; } cur.pb(s[i]); if (kth <4 ) cur.pb('.'); solve(s,i+1,kth+1,cur,ret); if (kth<4 ) cur.pp(); cur.pp(); if ( s[i]=='0' ) return; //two digits if ( i<len-1 ) { cur.pb(s[i]); cur.pb(s[i+1]); if (kth<4) cur.pb('.'); solve(s,i+2,kth+1,cur,ret); if ( kth<4) cur.pp(); cur.pp(); cur.pp(); } if (i <len-2) { int num= (s[i]-'0')*100+(s[i+1]-'0')*10+(s[i+2]-'0'); if ( num>255 ) return; cur.pb(s[i]); cur.pb(s[i+1]); cur.pb(s[i+2]); if ( kth<4 ) cur.pb('.'); solve(s,i+3,kth+1,cur,ret); if ( kth<4 ) cur.pp(); cur.pp(); cur.pp(); cur.pp(); } } };

上一篇:MyEclipse中引入Oracle 11g自带的JDBC包
下一篇:Shunsaku 应用场景 概要

相关文章

相关评论