Leetcode真题-恢复IP地址

一秉

问题描述：给定仅包含数字的字符串，请通过返回所有可能的有效IP地址组合来还原它。

一个有效的IP地址正好由四个整数（每个整数在0到255之间）组成，并用单点分隔。

例：输入： “ 25525511135” 输出： ["255.255.11.135", "255.255.111.35"]

解析：使用回溯法进行题解

代码：

class Solution {
    List<String> sol;
    public List<String> restoreIpAddresses(String s) {
        sol = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return sol;
        }
        
        dfs(s, 0, new StringBuilder());
        return sol;
    }
   
    void dfs(String s, int n, StringBuilder sb) {
        if (s.length() > 3 * (4 - n)) {
            // e.g. 2.2.25555555 is not possible
            return;
        }
        
        if (n == 4) {
            if (s.length() == 0) {
                sol.add(sb.toString());
            }
            return;
        }
        
        for (int i = 1; i <= 3; i++) {
            if (s.length() < i) {
                break;
            }
            String segment = s.substring(0, i);
            int value = Integer.parseInt(segment);
            if (value <= 255 && String.valueOf(value).length() == i) {
                // segment in range [0,255] and has no leading zero like 0x, 0xx
                StringBuilder tempSb = new StringBuilder(sb);
                tempSb.append(segment);
                tempSb.append(n == 3 ? "" : ".");
                dfs(s.substring(i, s.length()), n+1, tempSb);
            }
        }
    }
}