首页 > 代码库 > 【leetcode】Restore IP Addresses (middle)
【leetcode】Restore IP Addresses (middle)
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)
思路：回溯法 解向量X={str0, str1, str2, str3} 分别是IP地址的四段
判断每个解向量的部分时，先求出该部分最长和最短长度（根据后面每段最少1位，最多3位），回溯求解。符合条件时就把X按照要求的格式压入ans.
注意，判断每个部分是否有效时要排除00，01，001...等0开头的情况。
#include <iostream>#include <vector>#include <algorithm>#include <queue>#include <stack>using namespace std;class Solution {public: vector<string> restoreIpAddresses(string s) { vector<string> ans; int len = s.length(); if(len < 4) return ans; vector<string> X(4, ""); vector<vector<string>> S(4, vector<string>()); int k = 0; int maxlen = min(3, len - 3 * 1); int minlen = max(1, len - 3 * 3); for(int i = minlen; i <= maxlen; i++) { string sub = s.substr(0, i); if(isVaildIP(sub)) { S[0].push_back(sub); } } while(k >= 0) { while(!S[k].empty()) { X[k] = S[k].back(); S[k].pop_back(); if(k < 3) { k = k + 1; int startloc = 0; for(int j = 0; j < k; j++) { startloc += X[j].length(); } int maxlen = min(3, len - (4 - k - 1) * 1 - startloc); int minlen = max(1, len - (4 - k - 1) * 3 - startloc); for(int i = minlen; i <= maxlen; i++) { string sub = s.substr(startloc, i); if(isVaildIP(sub)) { S[k].push_back(sub); } } } else { ans.push_back(X[0]); for(int i = 1; i < 4; i++) { ans.back().append("."); ans.back().append(X[i]); } } } k--; } return ans; } bool isVaildIP(string snum) { if(snum.size() > 1 && snum[0] == ‘0‘) return false; int num = atoi(snum.c_str()); return (num >= 0 && num <= 255); }};int main(){ Solution s; string num =/* "25525511135"*/"010010"; vector<string> ans = s.restoreIpAddresses(num); return 0;}
【leetcode】Restore IP Addresses (middle)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。