LeetCode 93. 复原 IP 地址

作者:Choi Yang

更新于:5 个月前

字数统计:918 字

阅读时长:4 分钟

阅读量:

题目描述

给定一个只包含数字的字符串，复原它并返回所有可能的 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 地址。

示例 1：

javascript

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

javascript

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

javascript

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

javascript

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

javascript

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

提示：

javascript

0 <= s.length <= 3000
s 仅由数字组成

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/restore-ip-addresses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

直接看图解，显然要用回溯来做，我的做法是对于当前位置，我们可以有三种选择，选一个，选两个，还有选三个。此时就需要判断一下是不是会出现选出边界的情况。

然后对于我们选择的数字，要判断是否出现前导 0 ，同时也要看一下如果是三位数字的话，是不是会超过 255 。题目不能重复选择，于是用组合思想，免去 vis 数组。

借助大佬 xiao_ben_zhu 图解

javascriptcppjavapython

javascript

var restoreIpAddresses = function (s) {
  let res = [];
  let dfs = (cur, start) => {
    if (cur.length == 4 && start >= s.length) {
      res.push(cur.join("."));
      return;
    }
    if (cur.length == 4 && start != s.length) return;
    for (let k = 1; k <= 3; k++) {
      // 如果取的范围超过了字符串长度，直接剪掉
      if (start + k - 1 >= s.length) return;
      // 切割字符串
      let str = s.substring(start, start + k);
      if (str.length >= 2 && str[0] == 0) return;
      if (str.length >= 3 && +str > 255) return;
      cur.push(str);
      dfs(cur.slice(), start + k);
      // 回溯
      cur.pop();
    }
  };
  dfs([], 0);
  return res;
};

cpp

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        string ip;
        dfs(s, 0, 0, ip, res);
        return res;
    }
    void dfs(string s, int u, int k, string ip, vector<string>& res) {
        if (u == s.size()) {
            if (k == 4) {
                ip.erase(ip.end() - 1);
                res.push_back(ip);
            }
            return;
        }
        if (k == 4) return;
        for (int i = u, t = 0; i < s.size(); i++) {
            if (i > u && s[u] == '0') break;
            t = t * 10 + s[i] - '0';
            if (t <= 255) {
                ip += s[i];
                ip += '.';
                dfs(s, i + 1, k + 1, ip, res);
            } else {
                break;
            }
        }
    }
};

java

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        StringBuilder ip = new StringBuilder();
        for (int a = 1; a < 4; ++a)
            for (int b = 1; b < 4; ++b)
                for (int c = 1; c < 4; ++c)
                    for (int d = 1; d < 4; ++d) {
                        if (a + b + c + d == s.length()) {
                            int n1 = Integer.parseInt(s.substring(0, a));
                            int n2 = Integer.parseInt(s.substring(a, a + b));
                            int n3 = Integer.parseInt(s.substring(a + b, a + b + c));
                            int n4 = Integer.parseInt(s.substring(a + b + c));
                            if (n1 <= 255 && n2 <= 255 && n3 <= 255 && n4 <= 255) {
                                ip.append(n1).append('.').append(n2).append('.').append(n3).append('.').append(n4);
                                if (ip.length() == s.length() + 3) res.add(ip.toString());
                                ip.delete(0, ip.length());
                            }
                        }
                    }
        return res;
    }
}

python

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        SEG_COUNT = 4
        ans = list()
        segments = [0] * SEG_COUNT

        def dfs(segId: int, segStart: int):
            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
            if segId == SEG_COUNT:
                if segStart == len(s):
                    ipAddr = ".".join(str(seg) for seg in segments)
                    ans.append(ipAddr)
                return

            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么就不是一种答案
            if segStart == len(s):
                return

            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
            if s[segStart] == "0":
                segments[segId] = 0
                dfs(segId + 1, segStart + 1)

            # 一般情况，枚举每一种可能性并递归
            addr = 0
            for segEnd in range(segStart, len(s)):
                addr = addr * 10 + (ord(s[segEnd]) - ord("0"))
                if 0 < addr <= 0xFF:
                    segments[segId] = addr
                    dfs(segId + 1, segEnd + 1)
                else:
                    break

        dfs(0, 0)
        return ans

javascript

学如逆水行舟，不进则退

Contributors

Choi Yang

LeetCode 93. 复原 IP 地址 ​

题目描述 ​

解题思路 ​

Contributors ​

LeetCode 93. 复原 IP 地址

题目描述

解题思路

Contributors