leetcode 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地址组合,不能改变原先字符的顺序。

解题思路

首先需要判断字符串是否合法的条件: 1. 因为IP地址由4个字段组成,而且每个字段范围是0~255。 2. 字段长度大于1的时候不能以0未开头字符,比如10.00.1.00就是不允许的。 3. 每个字段的长度最多为3,整个字符串的长度至多为12,每个字段至少有一位,字符串的长度至少为4。而且当前字段的长度也有限制:

//下限,3为每个字段最多的长度,下限不可能小于1
int lower = 字符串总长度 - 剩余字段个数 * 3 > 1 ? 字符串总长度 - 剩余字段个数 * 3;
//上限,1为每个字段至少的长度,上限不可能大于3
int upper = 字符串总长度 - 剩余字段个数 * 1 < 3 ? 字符串总长度 - 剩余字段个数 * 1  : 3;

然后,对于这种不停的返回重组的题目,很容易想到回溯递归的算法,首先需要确定递归终止的条件,终止的条件有两种: 1. 已经到最后一个字段了,满足条件就加入结果集合中,然后终止,不满足直接终止 2. 在走到其中某个字段的途中,发现这个字段不满足条件,终止。

public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s.length() > 12 || s.length() < 4) return res;
        ipHelper(s, res, 3, new ArrayList<>());
        return res;
    }

/**
     * 
     * @param s 用来分析的字符串,是上一次去除选中字符串的结果
     * @param res 存放结果的集合
     * @param count 统计现在计算到第几个字段了
     * @param list 用来把不同的字符串组合成一个ip,同时也为了结合count方便删除不满足条件的字段
     */
    private void ipHelper(String s, List<String> res, int count, ArrayList<Integer> list) {
        if (count == 0) {
            int val = Integer.valueOf(s);
            if (s.length() > 1 && s.startsWith("0")) {
                return;
            } else if (val >= 0 && val <= 255) {
                list.add(val);
                StringBuilder sb = new StringBuilder();
                for (int k : list) {
                    sb.append(".").append(k);
                }
                res.add(sb.toString().substring(1));
                list.remove(3 - count);
                return;
            } else {
                return;
            }
        }
        //下限
        int lower = s.length() - count * 3 > 1 ? s.length() - count * 3 : 1;
        //上限
        int upper = s.length() - count < 3 ? s.length() - count : 3;
        if (lower > upper) {
            return;
        }
        for (int i = lower; i <= upper; i++) {
            String tmpString = s.substring(0, i);
            int val = Integer.valueOf(tmpString);
            if (i > 1 && tmpString.startsWith("0")) {
                return;
            } else if (val >= 0 && val <= 255) {
                list.add(val);
            } else
                return;
            ipHelper(s.substring(i), res, count - 1, list);
            list.remove(3 - count);
        }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏磐创AI技术团队的专栏

2018 年最常见的 Python 面试题 & 答案

https://data-flair.training/blogs/python-tutorial/

481
来自专栏机器学习入门

挑战程序竞赛系列(83):3.6计算几何基础

挑战程序竞赛系列(83):3.6计算几何基础 传送门:POJ 1127: Jack Straws 之前计算几何这一块还未学习,今天开始把它们补上。 题意: 桌...

1895
来自专栏维C果糖

编程思想 之「操作符」

在 Java 编程的过程中,我们对数据的处理,都是通过操作符来实现的。例如,用于赋值的赋值操作符、用于运算的运算操作符、用于比较的比较操作符,还包括逻辑操作符、...

4066
来自专栏Android机动车

数据结构学习笔记——串

枯眼望遥山隔水, 往来曾见几心知? 壶空怕酌一杯酒, 笔下难成和韵诗。 途路阻人离别久, 讯音无雁寄回迟。 孤灯夜守长寥寂, 夫忆妻兮父忆儿。

623
来自专栏Ryan Miao

Java String.split()用法小结

在java.lang包中有String.split()方法,返回是一个数组 我在应用中用到一些,给大家总结一下,仅供大家参考: 1、如果用“.”作为分隔的话,必...

31611
来自专栏Python小屋

Python正则表达式子模式扩展语法与应用

正则表达式语法实际上是独立于任何语言的,在大多数编程语言都可以使用相同的语法。常见正则表达式语法请参考Python使用正则表达式处理字符串 正则表达式使用圆括号...

2717
来自专栏Ryan Miao

String.split()用法以及特殊分隔符注意,ps:|

转载:http://www.cnblogs.com/mingforyou/archive/2013/09/03/3299569.html 在java.lang包...

2809
来自专栏编程理解

排序算法(四):归并排序

归并排序是通过分治的方式,将待排序集合拆分为多个子集合,对子集合排序后,合并子集合成为较大的子集合,不断合并最终完成整个集合的排序。

621
来自专栏有趣的Python

0-浙大攻略计划-专业课-c语言入门(慕课网)

C语言入门 -> Linux C语言编程基本原理与实践 -> Linux C语言指针与内存 -> Linux C语言结构体

1272
来自专栏C语言C++游戏编程

有人@我,你有一份C语言基础大全手册要领取,快来拿!

前两天,有网友问了我一个关于C语言的问题,本着认真装逼的态度,我把大学时学过的C语言课本翻了一遍,终于找到了答案。整理后,现分享给大家!

522

扫码关注云+社区