从原始 IP 字符串计算所有有效 IP 地址

Question

我正在解决 leetcode 问题 93. 恢复 IP 地址。

这是 url link：https://leetcode.com/problems/restore-ip-addresses/

描述如下：给定一个仅包含数字的字符串 s。 Return 可以从 s 获得的所有可能的有效 IP 地址。您可以 return 它们的顺序不限。

一个有效的IP地址恰好由四个整数组成，每个整数介于0到255之间，用单点分隔，不能有前导零。例如，“0.1.2.201”和“192.168.1.1”是有效的 IP 地址，“0.011.255.245”、“192.168.1.312”和“192.168@1.1”是无效的 IP 地址。

然而，当我试图通过回溯解决我的问题时，我无法弄清楚为什么我总是 return 一个空的 ArrayList。我仔细检查了我的基本情况和我的递归，但仍然找不到错误。任何帮助将不胜感激，谢谢！

public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if(s.length() == 0){
            return res;
        }
        int[] path = new int[4];
        snapshotIP(res,s,0,path,0);
        return res;
    }
    
    public void snapshotIP(List<String> res, String s, int index, int[] path, int segment){
        if(segment == 4 && index == s.length()){
            res.add(path[0]+"."+path[1]+"."+path[2]+"."+path[3]);
            return;
        }
        else if(segment == 4 || index == s.length()){
            return;
        }
        for(int len = 1; len <= 3 && index + len <= s.length(); len++){
            String snap = s.substring(index,index+len);
            int val = Integer.parseInt(snap);
            if(val > 225 || len >= 2 && s.charAt(index) == '0'){
                break;
            }
            path[segment] = val;
            snapshotIP(res,s,index+len,path,segment+1);
            path[segment] = -1; //undo the choice

        }
    }

Answer 1

你的代码看起来不错，一点也不差，但不确定你的错误在哪里。

这是一个替代解决方案，虽然不是很漂亮，但它会通过：

public final class Solution {
    public static final List<String> restoreIpAddresses(
        final String ip
    ) {
        List<String> res = new ArrayList<>();
        int length = ip.length();

        for (int i = 1; i < 4 && i < length - 2; i++)
            for (int j = i + 1; j < i + 4 && j < length - 1; j++)
                for (int k = j + 1; k < j + 4 && k < length; k++) {
                    final String part1 = ip.substring(0, i);
                    final String part2 = ip.substring(i, j);
                    final String part3 = ip.substring(j, k);
                    final String part4 = ip.substring(k, length);

                    if (isValid(part1) && isValid(part2) && isValid(part3) && isValid(part4)) {
                        res.add(part1 + "." + part2 + "." + part3 + "." + part4);
                    }
                }

        return res;

    }

    private static final boolean isValid(
        final String s
    ) {
        if (s.length() > 3 || s.length() == 0 || (s.charAt(0) == '0' && s.length() > 1) || Integer.parseInt(s) > 255) {
            return false;
        }

        return true;
    }
}

您的代码中有点可疑的是回溯辅助函数是 void，也许您必须定义一个变量才能使其工作，但仍然不确定。

与 C++ 类似，如果您有兴趣：

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    return 0;
}();


// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
#include <string>

#define LIMIT 256

using ValueType = std::uint_fast16_t;

static const struct Solution {
    static const std::vector<std::string> restoreIpAddresses(
        const std::string s
    ) {
        const ValueType len = std::size(s);
        std::vector<std::string> ips;
        std::string ip;
        ValueType a, b, c, d;
        ValueType A, B, C, D;

        for (a = 1; a < 4; ++a) {
            for (b = 1; b < 4; ++b) {
                for (c = 1; c < 4; ++c) {
                    for (d = 1; d < 4; ++d) {
                        if (a + b + c + d == len) {
                            A = std::stoi(s.substr(0, a));
                            B = std::stoi(s.substr(a, b));
                            C = std::stoi(s.substr(a + b, c));
                            D = std::stoi(s.substr(a + b + c, d));

                            if (A < LIMIT && B < LIMIT && C < LIMIT && D < LIMIT) {
                                ip = std::to_string(A) + "." +
                                     std::to_string(B) + "." +
                                     std::to_string(C) + "." +
                                     std::to_string(D);

                                if (std::size(ip) == len + 3) {
                                    ips.emplace_back(ip);
                                }
                            }
                        }
                    }
                }
            }
        }

        return ips;
    }
};

这是LeetCode的回溯深度优先搜索算法，跟你的差不多，希望能帮到你。

class Solution {
  int n;
  String s;
  LinkedList<String> segments = new LinkedList<String>();
  ArrayList<String> output = new ArrayList<String>();

  public boolean valid(String segment) {
    /*
    Check if the current segment is valid :
    1. less or equal to 255      
    2. the first character could be '0' 
    only if the segment is equal to '0'
    */
    int m = segment.length();
    if (m > 3)
      return false;
    return (segment.charAt(0) != '0') ? (Integer.valueOf(segment) <= 255) : (m == 1);
  }

  public void update_output(int curr_pos) {
    /*
    Append the current list of segments 
    to the list of solutions
    */
    String segment = s.substring(curr_pos + 1, n);
    if (valid(segment)) {
      segments.add(segment);
      output.add(String.join(".", segments));
      segments.removeLast();
    }
  }

  public void backtrack(int prev_pos, int dots) {
    /*
    prev_pos : the position of the previously placed dot
    dots : number of dots to place
    */
    // The current dot curr_pos could be placed 
    // in a range from prev_pos + 1 to prev_pos + 4.
    // The dot couldn't be placed 
    // after the last character in the string.
    int max_pos = Math.min(n - 1, prev_pos + 4);
    for (int curr_pos = prev_pos + 1; curr_pos < max_pos; curr_pos++) {
      String segment = s.substring(prev_pos + 1, curr_pos + 1);
      if (valid(segment)) {
        segments.add(segment);  // place dot
        if (dots - 1 == 0)      // if all 3 dots are placed
          update_output(curr_pos);  // add the solution to output
        else
          backtrack(curr_pos, dots - 1);  // continue to place dots
        segments.removeLast();  // remove the last placed dot 
      }
    }
  }

  public List<String> restoreIpAddresses(String s) {
    n = s.length();
    this.s = s;
    backtrack(-1, 3);
    return output;
  }
}

参考资料

有关更多详细信息，请参阅 Discussion Board where you can find plenty of well-explained accepted solutions with a variety of languages including low-complexity algorithms and asymptotic runtime/memory analysis^{1, 2}。

Answer 2

你写了一段相当高级的代码。它适用于所有 IP 地址段小于 225 的情况，但第一个测试用例在那里有 255s。

修复很简单，只需将“val > 225”替换为“val > 255”即可。

应该是这样的：

if(val > 255 || len >= 2 && s.charAt(index) == '0')

P.S。我会以不同的方式来做，我会在每个可能的地方添加点并验证每个收到的组合。

Answer 3

internal static IEnumerable<string> FetchPossibleIPs(string input, int currentSection = 1)
            {
                List<string> possibleIPs = new List<string>();
                if (input.Length > 0)
                {
                    // If section is 4 then no need 
                    // to break further and simply verify.
                    if (currentSection == 4)
                    {
                        if (int.Parse(input) <= 255 && input[0].ToString() != "0")
                        {
                            possibleIPs.Add(input);
                        }
                    }
                    // Else if section is < 4 then break the string 
                    // with substring of length of 1,2 or 3 to 
                    // figure out possible combinations.
                    else
                    {
                        for (int i = 1; i <= 3; ++i)
                        {
                            var section = input.Substring(0, i);
                            if (int.Parse(section) <= 255 && section[0].ToString() != "0")
                            {
                                var otherSections = FetchPossibleIPs(input.Substring(i), currentSection + 1);
                                foreach (var item in otherSections)
                                {
                                    possibleIPs.Add($"{section}.{item}");
                                }
                            }
                        }
                    }
                }
                return possibleIPs;
            }

C# 中使用递归求解的示例解决方案。它使用递归和回溯来解决问题。

从原始 IP 字符串计算所有有效 IP 地址

Computing All Valid IP Addresses From Raw IP String

java

backtracking

参考资料