[Leetcode] Restore IP Address 修复IP地址

VioletJack 发布于2019-08-14 12:26 / 693人阅读

摘要：四分法复杂度时间空间思路用三个点将字符串分成四段，验证每一段是否是有效的。注意使用时要确保所得到数不会超界。代码第一个分割点第二个分割点第三个分割点

Restore IP Address

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)

四分法 复杂度

时间 O(N^2) 空间 O(1)

思路

用三个点将字符串分成四段，验证每一段是否是有效的。我们只要控制这三个分割点就行了，注意约束条件有两个，一个是一段字符串不超过3个字母，另一个是控制好每段字符串最远结束的位置，比如第一个字符串最多延伸到倒数第4个字母。

注意

使用Integer.valueOf()时要确保所得到数不会超界。

代码

public class Solution {
    public List restoreIpAddresses(String s) {
        List res = new LinkedList();
        int len = s.length();
        // 第一个分割点
        for(int i = 1; i < 4 && i < len - 2; i++){
            // 第二个分割点
            for(int j = i + 1; j < i + 4 && j < len - 1; j++){
                // 第三个分割点
                for(int k = j + 1; k < j + 4 && k < len ; k++){
                    String s1 = s.substring(0,i), s2 = s.substring(i, j), s3 = s.substring(j, k), s4 = s.substring(k, s.length());
                    if(isValid(s1)&&isValid(s2)&&isValid(s3)&&isValid(s4)) res.add(s1+"."+s2+"."+s3+"."+s4);
                }
            }
        }
        return res;
    }
    
    private boolean isValid(String sub){
        return sub.length()<=3 && ((sub.charAt(0) != "0" && Integer.valueOf(sub) <=255) || sub.equals("0"));
    }
}

GPU云服务器云服务器 webrtc ip地址修复美国ip地址国外ip地址外网ip地址

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64483.html

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 [2...

Shisui 2019-08-14 14:28 评论0 收藏0
leetcode93. Restore IP Addresses

摘要：题目要求返回字符串能够组成的所有地址。思路与代码地址由位二进制数字构成，一共分为个区间，每个区间位。那么我们只要划分出这四个区间，然后判断这四个区间的值是否符合标准即可。题目要求 Given a string containing only digits, restore it by returning all possible valid IP address combinatio...

chenjiang3 2019-08-15 10:55 评论0 收藏0
[LeetCode] 93. Restore IP Addresses

Problem Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: 25525511135Output: [255.255.11.135, 255.255.111.35] Solution class So...

xingqiba 2019-08-16 13:58 评论0 收藏0
leetcode-93-Restore IP Addresses

摘要：题目描述题目理解将一段字符广度搜索截取，分别有种组合形式，添加限制条件，过滤掉不适合的组合元素。长度，大小，首字母应用如果进行字符串的子元素组合穷举，可以应用。所有的循环，利用到前一个状态，都可以理解为动态规划的一种分支题目描述：Given a string containing only digits, restore it by returning all possible va...

wmui 2019-07-31 11:11 评论0 收藏0
[LintCode/LeetCode] Restore IP Addresses

摘要：第一个分割点第二个分割点第三个分割点 Problem Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example Given 25525511135, return [ 255.255.11.135, 255....

bingo 2019-08-14 15:14 评论0 收藏0