专栏首页kevindroidleetcode 93. Restore IP Addresses

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 条评论
登录 后参与评论

相关文章

  • LeetCode242 Valid Anagram

    Given two strings s and t, write a function to determine if t is an anagram of s...

    用户1665735
  • LeetCode387 First Unique Character in a String

    Given a string, find the first non-repeating character in it and return it’s ind...

    用户1665735
  • LeetCode409 Longest Palindrome

    Given a string which consists of lowercase or uppercase letters, find the length...

    用户1665735
  • 聊聊hystrix的queueSizeRejectionThreshold参数

    本文主要研究一下hystrix的queueSizeRejectionThreshold参数

    codecraft
  • LeetCode题解—斐波那契数列

    写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

    码上积木
  • 分享|C# 中yield关键字解析

      前段时间了解到yield关键字,一直觉得还不错。今天给大家分享一下yield关键字的用法。yield return 返回集合不是一次性返回所有集合元素,而是...

    Vaccae
  • C# 中yield关键字解析

      前段时间了解到yield关键字,一直觉得还不错。今天给大家分享一下yield关键字的用法。yield return 返回集合不是一次性返回所有集合元素,而是...

    小世界的野孩子
  • SpringBoot+SpringSecurity处理Ajax登录请求

    最近在项目中遇到了这样一个问题:前后端分离,前端用Vue来做,所有的数据请求都使用vue-resource,没有使用表单,因此数据交互都是使用JSON,后台使用...

    田维常
  • SpringBoot+SpringSecurity处理Ajax登录请求

    最近在项目中遇到了这样一个问题:前后端分离,前端用Vue来做,所有的数据请求都使用vue-resource,没有使用表单,因此数据交互都是使用JSON,后台使用...

    江南一点雨
  • 经典算法面试题目-替换字符串的内容(1.5)

    Write a method to replace all spaces in a string with ‘%20’.

    谙忆

扫码关注云+社区

领取腾讯云代金券