leetcode-93 Restore IP Addresses

本文主要是介绍leetcode-93 Restore IP Addresses，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接: http://oj.leetcode.com/problems/restore-ip-addresses/ 

这道题的解法非常接近于NP问题，也是采用递归的解法。基本思路就是取出一个合法的数字，作为IP地址的一项，然后递归处理剩下的项。可以想象出一颗树，每个结点有三个可能的分支（因为范围是0-255，所以可以由一位两位或者三位组成）。并且这里树的层数不会超过四层，因为IP地址由四段组成，到了之后我们就没必要再递归下去，可以结束了。这里除了上述的结束条件外，另一个就是字符串读完了。可以看出这棵树的规模是固定的，不会像平常的NP问题那样，时间复杂度取决于输入的规模，是指数量级的，所以这道题并不是NP问题，因为他的分支是四段，有限制。代码如下：

class Solution {
public:vector<string> restoreIpAddresses(string s) {vector<string> res;if(s.size() < 4 || s.size() > 12) return res;helper(s,"",0,res);return res;}void helper(string s,string tmp,int count,vector<string> &res){if(count == 3){if(isValid(s)) res.push_back(tmp+s);return;}for(int i = 1; i < 4 && i < s.size(); i++){string subtmp = s.substr(0,i);if(isValid(subtmp))helper(s.substr(i),tmp+subtmp+'.',count+1,res);}}bool isValid(string str){

<span style="white-space:pre">	</span>if(str.size() <= 0) return false;int tmp = stoll(str);if(str[0] == '0' && str.size() > 1) return false;else if(tmp >=0 && tmp <= 255) return true;return false;}};

实现中需要一个判断数字是否为合法ip地址的一项的函数，首先要在0-255之间，其次前面字符不能是0。剩下的就是 NP问题 的套路了，递归中套一个for循环，不熟悉的朋友可以看看 N-Queens 哈

关于字符串的substr函数（http://www.cplusplus.com/reference/string/string/substr/）

string substr (size_t pos = 0, size_t len = npos) const;

Position of the first character to be copied as a substring.
If this is equal to the string length, the function returns an empty string.//在上面的函数helper中的第一个参数可能是""字符串
If this is greater than the string length, it throws out_of_range.
Note: The first character is denoted by a value of 0 (not 1).

stoll("")的值为多少了？

cpp.sh上运行的结果 Exit code: 0 (normal program termination)

ubuntu14.04上运行的结果：

terminate called after throwing an instance of 'std::invalid_argument'
  what():  stoll
Aborted (core dumped)

几点注意的地方：

1. 在验证字符串是否是数字的时候，要注意0的情况，001，010，03都是非法的（0是合法的）。所以，如果第一位取出来是0，那么我们就判断字符串是否是"0"，不是的情况都是非法的

2. 取字符串的时候，注意位数不够的问题，不仅<4, 而且<s.length()

3. 注意substring的范围

4. 字符串转换成数字 Integer.parseInt(); 

5. 别忘了IP 地址里面的 "."

6. 到第4个Part的时候我们就可以整体验证剩下的所有字符串（因为第4个Part最后一定要取到结尾才是正确的字符串）

参考：http://blog.csdn.net/linhuanmars/article/details/24683699

http://blog.csdn.net/u011095253/article/details/9158449

这篇关于leetcode-93 Restore IP Addresses的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---