个人免费建站系统,泰州网页制作,世界上最有趣的网站,怎么做网站投票选举文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;参照【算法与数据结构】131、LeetCode分割回文串的思路#xff0c;需要将IP字符串进行分割#xff0… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析参照【算法与数据结构】131、LeetCode分割回文串的思路需要将IP字符串进行分割同时要对分割字符串的合法性进行判断。IP字符串一共有四个子串前三个子串在for循环中找到最后咋终止条件中判断第四个子串是否合法如果合法则加入结果数组。 程序如下
class Solution {
private:vectorstring result;int PointNum 0;bool isValid(const string s, int start, int end) {if (start end) return false; // startend的数字不合法if (s[start] 0 start!end) return false; // 0开头的数字不合法 int num 0;for (int i start; i end; i) {if (s[i] 0 || s[i]9) return false;num num * 10 (s[i] - 0);if (num 255) return false;}return true;}void backtracking(string s, int startIndex) {if (PointNum 3) {if(isValid(s, startIndex, s.size()-1)) result.push_back(s); // 判断最后一个子串是否合法如果合法直接加入结果数组 return;}for (int i startIndex; i s.size(); i) { if (isValid(s, startIndex, i)) { // 判断子串是否合法s.insert(s.begin() i 1, .); // 插入分隔符PointNum;backtracking(s, i 2); // 递归PointNum--;s.erase(s.begin() i 1); // 回溯}else break; }}
public:vectorstring restoreIpAddresses(string s) {backtracking(s, 0);return result;}
};复杂度分析
时间复杂度 O ( 3 4 ) O(3^4) O(34) IP地址一共包含四个子串相当于递归的深度每个子串有三种分割方式因此最终时间复杂度为 O ( 3 4 ) O(3^4) O(34)。空间复杂度 O ( n ) O(n) O(n)。
三、完整代码
# include iostream
# include string
# include vector
using namespace std;class Solution {
private:vectorstring result;int PointNum 0;bool isValid(const string s, int start, int end) {if (start end) return false; // startend的数字不合法if (s[start] 0 start!end) return false; // 0开头的数字不合法 int num 0;for (int i start; i end; i) {if (s[i] 0 || s[i]9) return false;num num * 10 (s[i] - 0);if (num 255) return false;}return true;}void backtracking(string s, int startIndex) {if (PointNum 3) {if(isValid(s, startIndex, s.size()-1)) result.push_back(s); // 判断最后一个子串是否合法如果合法直接加入结果数组 return;}for (int i startIndex; i s.size(); i) { if (isValid(s, startIndex, i)) { // 判断子串是否合法s.insert(s.begin() i 1, .); // 插入分隔符PointNum;backtracking(s, i 2); // 递归PointNum--;s.erase(s.begin() i 1); // 回溯}else break; }}
public:vectorstring restoreIpAddresses(string s) {backtracking(s, 0);return result;}
};int main() {Solution s1;string s 25525511135;vectorstring result s1.restoreIpAddresses(s);for (vectorstring::iterator jt result.begin(); jt ! result.end(); jt) {cout *jt endl;}cout endl;system(pause);return 0;
}end
