[LeetCode83]Restore IP Addresses

本文主要是介绍[LeetCode83]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)

Analysis:

递归的将数字串分成四个部分，每个部分满足0<=p<=255。要注意一些边界case，比如010是没有意思的，“0.10.010.1”。

Java

public class Solution {public List<String> restoreIpAddresses(String s) {List<String> res = getIPAdd(s,4);if(res == null) res = new ArrayList<>();return res;}public ArrayList<String> getIPAdd(String s, int k){assert(k<=4 && k>=1);if(s==null || s.length()<k || s.length()>3*k) return null;ArrayList<String> res = new ArrayList<>();for(int i=0;i<Math.min(s.length(), 3);i++){String num = s.substring(0, i+1);if((i==0 || num.charAt(0)>'0')&& Integer.parseInt(num)<=255){if(k==1){if(i==s.length()-1)res.add(num);}else {ArrayList<String> remain = getIPAdd(s.substring(i+1), k-1);if(remain!=null){for(String r:remain){String temp = num+'.'+r;res.add(temp);}}}}elsebreak;}return res;}
}

c++

class Solution {
public:/*
s -- string, input
start -- startindex, start from which index in s
step -- step current step index, start from 0, valid value1-4,4 means the end
ip -- intermediate, split result in current spliting process
result -- save all possible ip address
*/
void dfsIp(string s, size_t start, size_t step, string ip,vector<string> &result){if(start == s.size() && step == 4){//find a possible resultip.resize(ip.size()-1);result.push_back(ip);return;}//since each part of IP address is in 0..255,the leagth of each// part is less than 3 and more than 0if(s.size()-start > (4-step)*3) return;if(s.size()-start < (4-step)) return;int num=0;for(size_t i=start;i<start+3;i++){num = num*10 + (s[i]-'0');if(num<=255){ip+=s[i];dfsIp(s,i+1,step+1,ip+'.',result);}if(num == 0) break;}
}
vector<string> restoreIpAddresses(string s) {vector<string> result;string ip; // save temporaty result in processingdfsIp(s,0,0,ip,result);return result;
}
};

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

---