复原IP地址

来自Leetcode第93题复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]

---

暴力

4层循环遍历解决所有情况。

public List<String> restoreIpAddresses(String s) {
    List<String> ret = new ArrayList<>();

    StringBuilder ip = new StringBuilder();

    for(int a = 1 ; a < 4 ; ++ a)
        for(int b = 1 ; b < 4 ; ++ b)
            for(int c = 1 ; c < 4 ; ++ c)
                for(int d = 1 ; d < 4 ; ++ d)
                {
                    if(a + b + c + d == s.length() )
                    {
                        int n1 = Integer.parseInt(s.substring(0, a));
                        int n2 = Integer.parseInt(s.substring(a, a+b));
                        int n3 = Integer.parseInt(s.substring(a+b, a+b+c));
                        int n4 = Integer.parseInt(s.substring(a+b+c));
                        if(n1 <= 255 && n2 <= 255 && n3 <= 255 && n4 <= 255)
                        {
                            ip.append(n1).append('.').append(n2)
                                    .append('.').append(n3).append('.').append(n4);
                            if(ip.length() == s.length() + 3) ret.add(ip.toString());
                            ip.delete(0, ip.length());
                        }
                    }
                }
    return ret;
}

回溯

来自题解

• 遍历三个有效位置curr_pos 以放置点。
  • 检查从上一个点到现在点中间的部分是否有效 :
  • 是 :
    • 放置该点。
    • 检查全部 3个点是否放好:
      • 是 :
        • 将结果添加到输出列表中。
      • 否 :
        • 继续放下一个点 backtrack(curr_pos, dots - 1)。
    • 回溯，移除最后一个点。

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) {
    List<String> res = new ArrayList<>();
    int n = s.length();
    backtrack(0, "", 4, s, res, n);
    return res;
}

private void backtrack(int i, String tmp, int flag, String s, List<String> res, int n) {
    if (i == n && flag == 0) {
        res.add(tmp.substring(0, tmp.length() - 1));
        return;
    }
    if (flag < 0) return;
    for (int j = i; j < i + 3; j++) {
        if (j < n) {
            if (i == j && s.charAt(j) == '0') {
                backtrack(j + 1, tmp + s.charAt(j) + ".", flag - 1, s, res, n);
                break;
            }
            if (Integer.parseInt(s.substring(i, j + 1)) <= 255)
                backtrack(j + 1, tmp + s.substring(i, j + 1) + ".", flag - 1, s, res, n);
        }
    }
}