问题描述 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)
解决思路 其实和之前的ksum的方法有点类似，就是回溯。每次取1，2，3个字符出来比较（这里要注意00连接一起的情况，总之最近对这些边界情况都很不明感，经常wa），直至取了4个数字。
代码
class Solution {public: vector<string> restoreIpAddresses(string s) { vector<string> result; helper(s,4,result,""); return result; } void helper(string s,int n, vector<string>& result, string cur_s) { if (s.size() < n) return; if (n == 1 && s.length() > 0 && s.length() < 4) { int num = atoi(s.c_str()); if (num > 255 || s.length() > 1 && s[0] == '0') return; cur_s += '.'; cur_s += s; result.push_back(cur_s); return; } for (int i = 0; i < 3 && i < s.length(); i++) { int num = atoi(s.substr(0,i+1).c_str()); if (num > 255 || i > 0 && s[0] == '0') break; if (n < 4) helper(s.substr(i+1),n-1,result,cur_s+'.'+s.substr(0,i+1)); else helper(s.substr(i+1),n-1,result,s.substr(0,i+1)); } }};新闻热点
疑难解答
