leetcode 93 Restore IP Addresses详解

1.题目

有效 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 中的任何数字。你可以按 任何 顺序返回答案。

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

输入：s = “0000” 输出：[“0.0.0.0”]

输入：s = “101023” 输出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

提示： 1 <= s.length <= 20 s 仅由数字组成

2.思路分析

这是一个典型的递归+DFS问题。我们可以将问题看成在字符串中加入三个点将字符串分为四段，而且要求四段都必须合法，即每一段都为[0, 255]之间。同时，当每一段只有一位时，该位可以为0。而每一段不止一位时，不能以0开头。

以k表示需要分的段数，k初始值设为4。如果k减到0，则说明分段工作已完成。如果此时字符串刚好为空，说明该分法符合要求，可以加入结果。

3.c++代码

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

bool isValid(string s) {
    if (s.size() > 1 && s[0] == 0) return false;
    return stoi(s) <= 255;
}

void dfs(string s, int k, string out, vector<string> &res) {
    if (k==0) {
        if (s.size() == 0) res.push_back(out);
    } else {
        for(int i=1; i<=3; i++) {
            if (s.size() >= i && isValid(s.substr(0, i))) {
                if (k==1) dfs(s.substr(i), k-1, out+s.substr(0, i), res);
                else dfs(s.substr(i), k-1, out+s.substr(0, i)+".", res);
            }
        }
    }
}

void run() {
    vector<string> vec;
    // string s = "25525511135";
    // string s = "101023";
    string s = "0000";
    dfs(s, 4, "", vec);
    for(string ele: vec) {
        cout<<ele<<endl;
    }
}

int main(int argc, char const *argv[])
{
    run();
    return 0;
}

上面的代码是直接将结果打印出来，如果需要改成题目的输出形式，只需要将对应的结果容器中的数据组织成对应的形式即可。