93. 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)

思路: 有效的IP地址由4段构成,每段最多3位数,数字在[0,255]区间范围内。
首先我们要对输入做些基本的边界判断,例如s是否为null, 4<=s.length()<=12.
我们可以用一个临时list来盛放每段的ip地址,最后把list 转化为String加入到最终结果List里面;
递归结束条件: 满足保存ip地址的临时list.size() == 4的情况下: 1. 记录当前位置的pos正好为给定字符串s的长度,否的话,返回; 2. 满足以上两个条件,就是一个合理解,把临时list转化为String加到最终结果List里面;
递归条件:从i=pos开始,到i < s.length() && i < pos + 3进行遍历,这是因为每段ip最多为3位数字构成; 对于每次求得的当前ip segment = s.substring(i, pos + 1); 调用isValid判断是否是合理的ip segment, 合理的话,加入到临时list;递归调用执行i+1步求解, 最后别忘了list中去除最后一个元素。

复杂度:

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null || s.length() < 4 || s.length() > 12) return res;
        helper(res, s, 0, new ArrayList<String>());
        return res;
    }

    public void helper(List<String> res, String s, int pos, List<String> ipList) {
        if (ipList.size() == 4) {
            if (pos != s.length()) return;
            res.add(convertListToString(ipList));
            return;
        }

        for (int i = pos; i < s.length() && i < pos + 3; i++) {
            String ipSeg = s.substring(pos, i+1);
            if (isValid(ipSeg)) {
                ipList.add(ipSeg);
                helper(res, s, i + 1, ipList);
                ipList.remove(ipList.size() - 1);
            }
        }
    }

    private boolean isValid(String s) {
        if (s == null || s.length() == 0) return false;
        if (s.charAt(0) == '0') {
            return s.equals("0");
        }
        int num = Integer.parseInt(s);
        return num > 0 && num < 256;
    }

    private String convertListToString(List<String> list) {
        StringBuilder sb = new StringBuilder();
        for (String s: list) {
            sb.append(s);
            sb.append(".");
        }
        String ipAddress = sb.toString();
        return ipAddress.substring(0, ipAddress.length() - 1);
    }
}

Reference:
https://segmentfault.com/a/1190000006245389

http://www.cnblogs.com/yrbbest/p/4437164.html

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s