Given a string containing only digits, restore it by returning all possible valid IP address combinations.

    Example:

    1. Input: "25525511135"
    2. Output: ["255.255.11.135", "255.255.111.35"]

    题意

    解析一段字符串，返回所有能构成有效IP地址的组合。

    思路

    有效的IP地址由四节组成，每一节的数字最多有三位且该数字不大于255，有多位的数字起始不能为0。

    利用回溯法进行处理。

    代码实现

    1. class Solution {
    2.     public List<String> restoreIpAddresses(String s) {
    3.         List<String> ans = new ArrayList<>();
    4.         if (s.length() > 12 || s.length() < 4) {
    5.             return ans;
    6.         }
    7.         dfs(s, 0, new StringBuilder(), 0, ans);
    8.         return ans;
    9.     }
    11.     private void dfs(String s, int pos, StringBuilder sb, int size, List<String> ans) {
    12.         if (pos == s.length() && size == 4) {
    13.             ans.add(sb.toString());
    14.             return;
    15.         } else if (size == 4) {
    16.             // 如果已经有四节，但还有字符没处理
    17.             return;
    18.         }
    20.         for (int i = 1; i <= 3; i++) {
    21.             if (pos + i > s.length() || i > 1 && s.charAt(pos) == '0') {
    22.                 break;
    23.             }
    24.             String t = s.substring(pos, pos + i);
    25.             if (Integer.parseInt(t) <= 255) {
    26.                 t = pos == 0 ? t : '.' + t;
    27.                 sb.append(t);
    28.                 dfs(s, pos + i, sb, size + 1, ans);
    29.                 sb.delete(sb.length() - t.length(), sb.length());
    30.             }
    31.         }
    32.     }
    33. }