1、解题思路

  1. 回溯法： 递归地尝试在每个位置插入分隔符（.），确保每个段满足IP地址的条件。终止条件：已经插入三个分隔符，且剩余字符串也满足条件。剪枝条件： 字符串太长或太短（总长度应在4到12之间）。当前段的数字不在[0,255]范围内。当前段有前导零且长度大于1。
  2. 条件检查： 段长度不超过3。段数字不超过255。段不能有前导零（除非是"0"本身）。

2、代码实现

C++
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串vector
     */
    vector<string> restoreIpAddresses(string s) {
        // write code here
        vector<string> result;
        backtrack(s, 0, "", 0, result);
        return result;
    }

  private:
    void backtrack(string s, int index, string current, int count, vector<string>& result) {
        if (count == 4) {
            if (index == s.size()) {
                result.push_back(current);
            }
            return ;
        }

        for (int i = 1; i <= 3 && index + i <= s.size(); ++i) {
            string segment = s.substr(index, i);
            if (isValid(segment)) {
                string new_current = current + segment + (count == 3 ? "" : ".");
                backtrack(s, index + i, new_current, count + 1, result);
            }
        }
    }

    bool isValid(string segment) {
        if (segment.size() > 1 && segment[0] == '0') {
            return false;
        }
        int num = stoi(segment);
        return num >= 0 && num <= 255;
    }
};
Java
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        ArrayList<String> result = new ArrayList<>();
        backtrack(s, 0, "", 0, result);
        return result;
    }

    private void backtrack(String s, int index, String current, int count, ArrayList<String> result) {
        if (count == 4) {
            if (index == s.length()) {
                result.add(current);
            }
            return;
        }
        for (int i = 1; i <= 3 && index + i <= s.length(); i++) {
            String segment = s.substring(index, index + i);
            if (isValid(segment)) {
                String newCurrent = current + segment + (count == 3 ? "" : ".");
                backtrack(s, index + i, newCurrent, count + 1, result);
            }
        }
    }

    private boolean isValid(String segment) {
        if (segment.length() > 1 && segment.charAt(0) == '0') {
            return false;
        }
        int num = Integer.parseInt(segment);
        return num >= 0 && num <= 255;
    }
}
Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return string字符串一维数组
#
class Solution:
    def restoreIpAddresses(self , s: str) -> List[str]:
        # write code here
        result = []
        self.backtrack(s, 0, "", 0, result)
        return result

    def backtrack(self, s: str, index: int, current: str, count: int, result: List[str]) -> None:
        if count == 4:
            if index == len(s):
                result.append(current)
            return
        for i in range(1, 4):
            if index + i > len(s):
                break
            segment = s[index:index + i]
            if self.is_valid(segment):
                new_current = current + segment + ("" if count == 3 else ".")
                self.backtrack(s, index + i, new_current, count + 1, result)

    def is_valid(self, segment: str) -> bool:
        if len(segment) > 1 and segment[0] == '0':
            return False
        num = int(segment)
        return 0 <= num <= 255

3、复杂度分析

  1. 递归终止条件： 已经插入三个分隔符（.），且剩余字符串为空。
  2. 剪枝条件： 当前段长度不超过3。当前段数字在[0,255]范围内。当前段不能有前导零（除非是"0"本身）。
  3. 复杂度分析： 时间复杂度：O(n!)，因为每个位置的分隔符选择都影响后续的选择。空间复杂度：O(n!)，存储所有可能的合法IP地址。

进阶思考

  • 如果需要优化剪枝条件，可以在递归前先检查字符串长度（4 ≤ n ≤ 12）。
  • 如果需要处理更长的字符串（如 n ≤ 20），可以考虑动态规划或其他优化方法。