Problem:
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
思路：
首先弄清楚IP地址的定义。
Definition of valid IP address:
1. The length of the ip without '.' should be equal to the length of s;
2. The digit order of ip should be same as the dight order of s;
3. Each part separated by the '.' should not start with '0' except only '0';
4. Each part separated by the '.' should not larger than 255.
题目给出的是一串数字组成的字符串，将它转化成IP地址，实际上也就是将其转化为4块，然后每块的值不能超过255（意味着该子串的长度在区间[1,3]内）。因此首先需要找到4个[1,3]的数，它们之和等于s的长度。再进行筛选，看是否每一个数都小于或等于255。需要注意的是，每一块是不能以0为开头的，所以类似于"01.1.1.1"这样的IP地址是错误的，如果有一块包含有0，那么这一块只能为0,例如"0.10.0.100"，这样的IP地址是正确的。
Solution:
vector<string> restoreIpAddresses(string s) {
vector<string> res;
string ip_add;
for (int a = 1; a <= 3; a++)
for (int b = 1; b <= 3; b++)
for (int c = 1; c <= 3; c++)
for (int d = 1; d <= 3; d++)
if (a+b+c+d == s.length()) {
int A = stoi(s.substr(0, a)); //这里使用的stoi()函数比较巧妙，如果有一块是以0开头的字符，则转化为数字的时候就会丢掉，从而不构成一个IP地址
int B = stoi(s.substr(a, b));
int C = stoi(s.substr(a+b, c));
int D = stoi(s.substr(a+b+c, d));
if (A<=255 && B<=255 && C<=255 && D<=255) {
ip_add = to_string(A) + "." + to_string(B) + "." + to_string(C) + "." + to_string(D);
if (ip_add.length() == s.length() + 3)
res.push_back(ip_add);
}
}
return res;
}
性能：
Runtime: 0 ms Memory Usage: 8.6 MB
