本文主要是介绍[力扣题解]93. 复原 IP 地址,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:93. 复原 IP 地址
思路
回溯法;
特别的是,用pointNum
来记录.
的数量,并且没有创建path
,而是直接在原来的strings
中插入.
;
同时,在判断子串合法性的时候,0
是合法的,01
、00
是不合法的;
代码
Method 1
class Solution {
public:vector<string> result; //void backtracking(string& s, int startIndex, int pointNum){int i;if(pointNum == 3){string temp1 = s.substr(startIndex, s.size()-startIndex);if(isValid(temp1)){result.push_back(s);}return;}for(i = startIndex; i < s.size(); i++){// 判断子区间[startIndex, i]是否合法ßstring temp2 = s.substr(startIndex, i-startIndex+1);if(isValid(temp2)){s.insert(s.begin()+i+1, '.'); //你为什么要加一个s.begin()// pointNum++;backtracking(s, i+2, pointNum+1);// pointNum--;s.erase(s.begin()+i+1);}// 不合法, 直接结束else{break;}}}// 使用 istringstreambool isValid(const string& s){// 为空也不行if(s.empty()){return false;}int num;istringstream ss(s);ss >> num;// 0 <= num <= 255if(!(num >= 0 && num <= 255)){return false;}// 00 也不可以if(s.size() > 1 && s[0] == '0'){ return false;}return true;}vector<string> restoreIpAddresses(string s) {result.clear();if(s.size() < 4 || s.size() > 12){return result;}backtracking(s, 0, 0);return result;}
};
回溯pointNum
用这个:backtracking(s, i+2, pointNum+1);
Method 2
class Solution {
public:vector<string> result; //void backtracking(string& s, int startIndex, int pointNum){int i;if(pointNum == 3){string temp1 = s.substr(startIndex, s.size()-startIndex);if(isValid(temp1)){result.push_back(s);}return;}for(i = startIndex; i < s.size(); i++){// 判断子区间[startIndex, i]是否合法ßstring temp2 = s.substr(startIndex, i-startIndex+1);if(isValid(temp2)){s.insert(s.begin()+i+1, '.'); //你为什么要加一个s.begin()pointNum++;backtracking(s, i+2, pointNum);pointNum--;s.erase(s.begin()+i+1);}// 不合法, 直接结束else{break;}}}// 使用 istringstreambool isValid(const string& s){// 为空也不行if(s.empty()){return false;}int num;istringstream ss(s);ss >> num;// 0 <= num <= 255if(!(num >= 0 && num <= 255)){return false;}// 00 也不可以if(s.size() > 1 && s[0] == '0'){ return false;}return true;}vector<string> restoreIpAddresses(string s) {result.clear();if(s.size() < 4 || s.size() > 12){return result;}backtracking(s, 0, 0);return result;}
};
回溯pointNum
用这个:
pointNum++;
pointNum--;
Method 3
类似于C的写法,基础方法,求出string代表的int;
bool isValid(const string& s, int start, int end){int i = 0;int num = 0;// 一直喜欢用各种奇奇怪怪函数的carl怎么没借助C++专门的工具?if(start > end){return false;}// '0' 开头的数字不合法, 不包括数字'0'if(s[start] == '0' && start != end){return false;}for(i = start; i <= end; i++){// 遇到非数字字符不合法// if(!(s[i] >= 0 && s[i] <= 9))if(s[i] > '9' || s[i] < '0'){return false;}num = num * 10 + (s[i] - '0');// 如果大于255, 不合法if(num > 255){return false;}}return true;}
疑问
上述代码中使用了string.insert(s.begin()+i+1, '.')
的方式来进行插入操作,而我随便搜索的教程里没有用迭代器s.begin()
来表示插入位置的,都是直接用序号,比如string(i+1, ".")
,然而我这么写力扣反而报错了,很奇怪,很奇怪;
这篇关于[力扣题解]93. 复原 IP 地址的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!