Restore IP Addresses

描述

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

For example:Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

分析

必须要走到底部才能判断解是否合法，深搜。

代码

  1. // Restore IP Addresses
  2. // 时间复杂度O(n^4)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<String> restoreIpAddresses(String s) {
  5.         List<String> result = new ArrayList<>();
  6.         List<String> ip = new ArrayList<>();; // 存放中间结果
  7.         dfs(s, ip, result, 0);
  8.         return result;
  9.     }
  11.     /**
  12.      * 解析字符串
  13.      * @param[in] s 字符串，输入数据
  14.      * @param[out] ip 存放中间结果
  15.      * @param[out] result 存放所有可能的IP地址
  16.      * @param[in] start 当前正在处理的 index
  17.      * @return 无
  18.      */
  19.     private static void dfs(String s, List<String> ip,
  20.                             List<String> result, int start) {
  21.         if (ip.size() == 4 && start == s.length()) {  // 找到一个合法解
  22.             result.add(ip.get(0) + '.' + ip.get(1) + '.' +
  23.                     ip.get(2) + '.' + ip.get(3));
  24.             return;
  25.         }
  27.         if (s.length() - start > (4 - ip.size()) * 3)
  28.             return;  // 剪枝
  29.         if (s.length() - start < (4 - ip.size()))
  30.             return;  // 剪枝
  32.         int num = 0;
  33.         for (int i = start; i < start + 3 && i < s.length(); i++) {
  34.             num = num * 10 + (s.charAt(i) - '0');
  36.             if (num < 0 || num > 255) continue;  // 剪枝
  38.             ip.add(s.substring(start, i + 1));
  39.             dfs(s, ip, result, i + 1);
  40.             ip.remove(ip.size() - 1);
  42.             if (num == 0) break;  // 不允许前缀0，但允许单个0
  43.         }
  44.     }
  46.     public static void main(String[] args) {
  47.         Solution s = new Solution();
  48.         s.restoreIpAddresses("1111");
  49.     }
  50. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dfs/restore-ip-addresses.html