回溯法

class Solution { static final int SEC_COUNT = 4; List<String> ans = new ArrayList<>(); int[] segments = new int[SEC_COUNT]; public List<String> restoreIpAddresses(String s) { dfs(s, 0, 0); return ans; } private void dfs(String s, int segId, int segStart) { // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案 if (segId == SEC_COUNT && segStart == s.length()) { StringBuffer ipAddr = new StringBuffer(); for (int i = 0; i < SEC_COUNT; i++) { ipAddr.append(segments[i]); if (i != SEC_COUNT - 1) { ipAddr.append("."); } } ans.add(ipAddr.toString()); return; } // 如果还没右找到4段ip，就遍历完了字符串 或者 找到了4段ip但是还没遍历完字符串则回溯 if (segStart == s.length() || segId == SEC_COUNT) return; // 由于不能有前导0，如果当前数字ip为0那么只能为0 if (s.charAt(segStart) == '0') { segments[segId] = 0; dfs(s, segId + 1, segStart + 1); } // 枚举每段的每一种可能性然后递归 int addr = 0; for (int segEnd = segStart; segEnd < s.length(); segEnd++) { addr = addr * 10 + (s.charAt(segEnd) - '0'); if (addr > 0 && addr <= 0xFF) { segments[segId] = addr; dfs(s, segId + 1, segEnd + 1); } else { break; } } } }