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)
【leetcode做题笔记|leetcode:Restore IP Addresses】
Hide Tags Backtracking String
t题目地址：https://oj.leetcode.com/problems/restore-ip-addresses/
解题思路：
题目提示用回溯法做，我没有那么做。。为啥呢。。当然是不会呀。。。等我一会儿学了回溯法在来做一遍吧。
我用了比较土的办法来做，定义三个变量loc1,loc2,loc3分别来记录三个点所在的位置。然后对切分的字符进行判断，如果4个字段都满足IP的要求就添加进结果。
对字段的判断要求：
1，可以在循环时控制前3个字段的长度（大于等于1小于等于3）（第四个字段由字符串减去前面3个字段得到）
2，字段不能以0开头，不能大于255
代码：
class Solution {
public:
vector restoreIpAddresses(string s) {
int len=s.length();
vector ret;
if(len<=3||len>12) return ret;
int loc1,loc2,loc3;
for(loc1=1;
loc1<=3&&loc1255||s1.size()>1&&s1[0]=='0') continue;
for(loc2=loc1+1;
loc2<=loc1+3&&loc2<=len-2;
loc2++){
string s2=s.substr(loc1,loc2-loc1);
if(stoi(s2.c_str())>255||s2.size()>1&&s2[0]=='0') continue;
for(loc3=loc2+1;
loc3<=loc2+3&&loc3<=len-1;
loc3++){
string s3=s.substr(loc2,loc3-loc2);
if(atoi(s3.c_str())>255||s3.size()>1&&s3[0]=='0') continue;
string s4=s.substr(loc3);
if(s4.length()>3||atoi(s4.c_str())>255||s4.size()>1&&s4[0]=='0') continue;
string tmp=s1+"."+s2+"."+s3+"."+s4;
//cout< 
