首页 > itarticle > restore ip addresses

restore ip addresses

admin 11月 11, 2020 0

Problem

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地址的特性就好了。IP地址分为四个部分，每个部分以‘.’隔开且每个部分的值不能大于255。其余的就是backtracking就好了。

public class  {
    public List<String> restoreIpAddresses(String s) {
        List<String> ret = new LinkedList<>();
        if (s == null || s.length() < 4) return ret;
        StringBuilder sb = new StringBuilder();
        helper(s, ret, sb, 0, 0);
        return ret;
    }
    
    private void helper(String s, List<String> ret, StringBuilder sb, int part, int start) {
        int length = sb.length();
        if (part == 3) {
            int size = s.substring(start).length();
            if (size == 1 ||(size > 1 && size < 4 && s.charAt(start) != '0' && Integer.valueOf(s.substring(start)) <= 255)) {
                sb.append(s.substring(start));
                ret.add(sb.toString());
                sb.setLength(length);
            }
            
            return;
        }
        for (int i = start + 1; i < Math.min(start + 4, s.length()); i++) {
            String now = s.substring(start, i);
            if (now.length() == 1 || (now.charAt(0) != '0' && Integer.valueOf(now) <= 255)) {
                sb.append(now).append(".");
                helper(s, ret, sb, part + 1, i);
                sb.setLength(length);
            }
        }
    }
}