首页 > 代码库 > LeetCode: Restore IP Addresses
LeetCode: Restore IP Addresses
LeetCode: 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)
地址：https://oj.leetcode.com/problems/restore-ip-addresses/
算法：递归构造。一个ip地址有四个数字，每个数字必须在0到255之间，并且不能第一个非零数字不能以零开头。基本的思想是，取最后一个数字，看其是否合理，如果合理在递归构造前面三个数字；取最后两个数字，如果合理在递归前面三个数字；取最后三个数字，如果合理在递归构造前面三个数字。代码：
1 class Solution { 2 public: 3 vector<string> restoreIpAddresses(string s) { 4 vector<string> result; 5 partitionIpAddresses(s,4,result); 6 return result; 7 } 8 bool partitionIpAddresses(string s, int n, vector<string> &result){ 9 if(n <= 0 || s.empty()){10 return false;11 }12 if(n == 1){13 int val = atoi(s.c_str());14 if(val < 256 && isValidataion(s)){15 result.push_back(s);16 return true;17 }else{18 return false;19 }20 }21 int i = s.size() - 1;22 int val = atoi(s.substr(i,1).c_str());23 vector<string> temp;24 bool flag = partitionIpAddresses(s.substr(0,s.size()-1), n-1, temp);25 if(flag){26 for(int j = 0; j < temp.size(); ++j){27 if(isValidataion(s.substr(i,1)))28 result.push_back(temp[j] + "." + s.substr(i,1));29 }30 }31 temp.clear();32 --i;33 if(i >= 0){34 val = atoi(s.substr(i,2).c_str());35 flag = partitionIpAddresses(s.substr(0,s.size()-2), n-1, temp);36 if(flag){37 for(int j = 0; j < temp.size(); ++j){38 if(isValidataion(s.substr(i,2)))39 result.push_back(temp[j] + "." + s.substr(i,2));40 }41 }42 }43 temp.clear();44 --i;45 if(i >= 0){46 val = atoi(s.substr(i,3).c_str());47 if(val < 256){48 flag = partitionIpAddresses(s.substr(0,s.size()-3), n-1, temp);49 if(flag){50 for(int j = 0; j < temp.size(); ++j){51 if(isValidataion(s.substr(i,3)))52 result.push_back(temp[j] + "." + s.substr(i,3));53 }54 }55 }56 }57 return !result.empty();58 }59 bool isValidataion(const string &s){60 if(s.size() < 1) return false;61 if(s.size() == 1) return true;62 if(s[0] == ‘0‘) return false;63 return true;64 }65 };
LeetCode: Restore IP Addresses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。