复原IP地址

题目描述

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 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 = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
//样例二
输入：s = "0000"
输出：["0.0.0.0"]
//样例三
输入：s = "1111"
输出：["1.1.1.1"]    
//样例四
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
//样例五
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

题目分析

采用dfs回溯算法，每次dfs只分析IP地址中的其中一段，这样就会有函数dfs(string s, int id, int start)。其中id是当前分析的段数，start是此段从哪开始分析。

但是会有三个条件判断：

• 已经分析出来了：id=4且strat=s.length。那么就直接把结果存放到res这个结果字符串数组中。
• 分析到尾但是没有四段：s.length=strat。那么就直接返回。
• 当前分析的第一个数字是0：s[start]=‘0‘。那么只能作为单独一段，因为不允许有前导0。

接下来就是函数分析主体：

会从start开始每次取一个数字分析下一段（for循环）,也就是分析当前IP地址的第Id段为1、2、3位数字的情况。如果分析不成功，根据递归调用会回溯到上一个分析的状态。

代码实现

#include <iostream>
#include<string>
#include<vector>
using namespace std;

vector<string> res;
int num[4];


void dfs(string s, int id, int start) {
    if (id == 4) {
        if (start == s.length()){
            string str;
            str = str + to_string(num[0]) + ‘.‘ + to_string(num[1]) + ‘.‘ + to_string(num[2]) + ‘.‘ + 		             to_string(num[3]);
            res.push_back(str);
        }
        return;
    }//已经分析出来了

    if (start == s.length())
        return;
    //分析到尾但是没有四段

    if (s[start] == ‘0‘) {
        num[id] = 0;
        dfs(s, id + 1, start + 1);
    }
    //当前分析的第一个数字是0

    int addr = 0;//存放当前第id段的地址
    for (int i = start; i < s.length(); i++) {
        addr = addr * 10 + s[i] - ‘0‘;
        if (addr > 0 && addr < 256) {
            num[id] = addr;
            dfs(s, id + 1, i + 1);
        }
        else break;
    }

}


int main()
{
    string s;
    cin >> s;
    dfs(s, 0, 0);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i]<<endl;
    }
    return 0;
}

复原IP地址

原文：https://www.cnblogs.com/MrDaddy/p/14845117.html