LeetCode: Restore IP Addresses 解题报告

Restore IP Addresses

My Submissions

Question

Solution

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)

SOLUTION 1:

如果有跟过主页君的讲解，就会知道，这又是一道相当经典的DFS模板题目。我们照样套用http://www.ninechapter.com/的递归

模板，退出条件是：path.size == 4.

在模板中，我们加入一些判断条件来中断循环：例如说判断pre的字符串转化后的数字是不是在255以内。

另外，我们要排除055这种数字，所以加入这一行判断：

if (s.charAt(index) == '0' && i > index) {
　　break;
}

虽然是很简单的递归题，但主页君是真心用心写了的。而且这是相当经典的递归模板。同学们一定要记住这种模板解法哦！

 public List<String> restoreIpAddresses(String s) {

         if (s == null) {

             return null;

         }

         ArrayList<String> ret = new ArrayList<String>();

         ArrayList<String> path = new ArrayList<String>();

         dfs(s, 0, path, ret);

         return ret;

     }

     public void dfs(String s, int index, ArrayList<String> path, ArrayList<String> ret) {

         if (path.size() == 4) {

             if (index == s.length()) {

                 StringBuilder sb = new StringBuilder();

                 for (String str: path) {

                     sb.append(str);

                     sb.append('.');

                 }

                 sb.deleteCharAt(sb.length() - 1);

                 ret.add(sb.toString());

             }

             return;

         }

         int len = s.length();

         for (int i = index; i < index + 3 && i < len; i++) {

             if (s.charAt(index) == '0' && i > index) {

                 break;

             }

             String pre = s.substring(index, i + 1);

             int num = Integer.parseInt(pre);

             if (num > 255) {

                 continue;

             }

             path.add(pre);

             dfs(s, i + 1, path, ret);

             path.remove(path.size() - 1);

         }

     }

2015.1.1 redo:

容易出错的点：1. i的索引，注意不要越界。2. 记得把sb添加到ret中。

 public class Solution {

     public List<String> restoreIpAddresses(String s) {

         List<String> ret = new ArrayList<String>();

         // Bug 1: not length, but length().

         if (s == null || s.length() < 4 || s.length() > 12) {

             return ret;

         }

         dfs(s, new ArrayList<String>(), ret, 0);

         return ret;

     }

     public void dfs(String s, List<String> path, List<String> ret, int index) {

         // THE BASE CASE:

         int len = s.length();

         if (path.size() == 4) {

             // Create a solution.

             if (index == len) {

                 StringBuilder sb = new StringBuilder();

                 for (String str: path) {

                     sb.append(str);

                     sb.append(".");

                 }

                 sb.deleteCharAt(sb.length() - 1);

                 // bug 3: forget this statement.

                 ret.add(sb.toString());

             }

             return;

         }

         // 2/ 25 / 255

         // bug 2: i should < len.

         for (int i = index; i < index + 3 && i < len; i++) {

             String sub = s.substring(index, i + 1);

             if (s.charAt(index) == '0' && i != index) {

                 // only allow 0, not 02, 022

                 break;

             }

             if (!isValid(sub)) {

                 continue;

             }

             path.add(sub);

             dfs(s, path, ret, i + 1);

             path.remove(path.size() - 1);

         }

     }

     public boolean isValid(String s) {

         int num = Integer.parseInt(s);

         return num >= 0 && num <= 255;

     }

 }

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/RestoreIpAddresses.java

巴特西

LeetCode: Restore IP Addresses 解题报告

最新文章

热门文章