本文共 2565 字,大约阅读时间需要 8 分钟。
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example 1:
Given “25525511135”, return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)没有给出.
这道题的意思是给定一个仅包含数字的字符串,找到所有由该字符串组成的合法的IP地址。需要注意以下细节:
1.IP地址需要用到整个字符串,因此例子“25525511135”就只能是”255.255.11.135”和”255.255.111.35”。 2.IP地址由四段组成,每一段的范围都是0-255,并且不能有前导零。 解题的思想是递归跟回溯。在一次递归调用中使用变量count记录当前计算的是哪一段地址,当count等于3时(以0表示第一段)就对应计算第四段的数值,如果数值有效则添加到结果中去,否则返回;如果count为0,1,2则需要通过循环依次尝试截取1,2,3个字符作为当前段的数值,只在数值有效时才递归计算下一段。 整个流程不好描述,建议结合下面我的代码理解整个解题思想。通过之后看了一下其他大神的解法,除了递归,还有更直接暴力的方法,用四重循环进行判断,因为每一段的字符只能是1-3个,所以利用循环枚举所有可能的组合再保存正确的结果即可。见下面的其他代码。
class Solution {public: void dfs(vector&result, string &s, string temp, int start, int count) { string sub = ""; if (count == 3) { if (start >= s.length() || s.length() - start > 3) return ; sub = s.substr(start); if (!((sub.size() > 1 && sub[0] == '0') || (atoi(sub.c_str()) > 255))) { temp += sub; result.push_back(temp); } } else { for (int i = 1; i <= 3 && start + i <= s.length(); i++) { sub = s.substr(start, i); if (!((sub.size() > 1 && sub[0] == '0') || (atoi(sub.c_str()) > 255))) { dfs (result, s, temp + sub + ".", start + i, count + 1); } } } } vector restoreIpAddresses(string s) { vector result; dfs(result, s, "", 0, 0); return result; }};
class Solution {public: vectorrestoreIpAddresses(string s) { vector ret; string ans; for (int a=1; a<=3; a++) for (int b=1; b<=3; b++) for (int c=1; c<=3; c++) for (int d=1; d<=3; d++) if (a+b+c+d == s.length()) { int A = stoi(s.substr(0, a)); int B = stoi(s.substr(a, b)); int C = stoi(s.substr(a+b, c)); int D = stoi(s.substr(a+b+c, d)); if (A<=255 && B<=255 && C<=255 && D<=255) if ( (ans=to_string(A)+"."+to_string(B)+"."+to_string(C)+"."+to_string(D)).length() == s.length()+3) ret.push_back(ans); } return ret; }};
这道题一开始没有注意到要利用整个字符串,所以wrong了几次,后面才从例子中发现端倪,其实整个题目并不困难,关键是处理好边界以及数值范围的判断,理清楚递归的参数和返回条件就能做出来。
完成了这周的题目,继续去弄课程项目,这几周真是忙得不行,希望快点过去吧,加油加油~转载地址:http://xqntb.baihongyu.com/