LeetCode-复原 IP 地址（C++）

93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：
输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]

思路：这道题与分割回文串相似，同样用到了回溯算法，对字符串进行分割，

首先定义全局变量result为结果集。

回溯算法三部曲：

1. 确定回溯函数参数和返回值：参数为字符串s，递归遍历的起始位置startIndex和添加点的数量pointNum，返回类型为void。
2. 确定终止条件：当已经添加三个点之后，说明已经将字符串分割成了四段，然后判断最后一段字符串是否符合条件(之前三段已经在for循环内判断过，符合条件才能到第四段)，如果符合将s加入结果集，return。
3. 确定单层回溯逻辑：for循环横向遍历所有字符，定义起始位置startIndex，判断子串[startIndex, i] 是否符合条件，如果符合在i之后插入一个点，然后pointNum++。递归往深处遍历，递归的起始位置为i+2，因为在i之后插入了一个点，要跳过这个点。然后回溯，pointNum–，移除在i之后插入的点。

判断子串是否符合条件时，要判断子串如果长度大于1，那么首字符是否为0；判断子串是否大于255，如果符合有效ip地址的要求，返回true。

代码：

class Solution {	//93. 复原 IP 地址
public:
	vector<string> result;
	bool isValid(string const& s, int start, int end) {
		if (start > end) return false;
		if (s[start] == '0' && start != end) return false;
		int num = 0;
		for (int i = start; i <= end; ++i) {
			if (s[i] > '9' || s[i] < '0') return false;
			num = num * 10 + (s[i] - '0');
			if (num > 255)return false;
		}
		return true;
	}
	void backtracking(string& s, int pointNum, 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, pointNum, i + 2);
				pointNum--;
				s.erase(s.begin() + i + 1);
			}
			else break;
		}
	}
	vector<string> restoreIpAddresses(string s) {
		if (s.size()<4 || s.size()>12) return result;
		backtracking(s, 0, 0);
		return result;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

参考资料：代码随想录