资讯专栏INFORMATION COLUMN

LeetCode: 93. Restore IP Addresses

Shisui / 1389人阅读

摘要:以剩下的字符串,当前字符串,剩余单元数传入下一次递归。结束条件字符串长度为,并且剩余单元数为

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,最小为0

每个部分最长3位

可以得到几个限制:

给定字符串只包含数字

给定字符串最长为12,最短为4

每个部分最大255,最小为0

每个部分最长3位,0开头则只能为1位

算法分析:

总数4个单元,从传入字符串中每次截取开头1到最长3个字符(长度不超过当前字符串长度)作为当前单元,忽略不符合限制的数字,加入到当前得到的ip字符串。以剩下的字符串,当前ip字符串,剩余单元数传入下一次递归。

结束条件:

字符串长度为0,并且剩余单元数为0

public class Solution 
{
    public List restoreIpAddresses(String s) 
    {
        List res = new ArrayList<>();
        
        if (s == null || s.length() == 0)
        {
            return res;
        }
        
        helper(s, "", 4, res);
        
        return res;
    }
    
    public void helper(String input, String cur, int partNum, List res)
    {
        if (input == null)
        {
            return;
        }
        
        if (input.length() > partNum * 3 || input.length() < partNum)
        {
            return;
        }
        
        if (input.length() == 0 && partNum == 0)
        {
            res.add(cur);
            return;
        }
        
        for (int i = 1; i <= 3 && i <= input.length(); i++)
        {
            String curTemp = input.substring(0,i);
            String rest = input.substring(i);
            
            if (isValid(curTemp))
            {
                String temp = new String(cur);
                temp += curTemp;
                
                if (partNum > 1)
                {
                    temp += ".";
                }
                
                helper(rest, temp, partNum-1, res);
            }
        }
    }
    
    public boolean isValid(String s)
    {
        if (s.charAt(0) == "0")
        {
            return s.equals("0");
        }
        
        int temp = Integer.parseInt(s);
        
        return temp > 0 && temp <= 255;
    }
}

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

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

相关文章

  • leetcode93. Restore IP Addresses

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

    chenjiang3 评论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 评论0 收藏0
  • leetcode-93-Restore IP Addresses

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

    wmui 评论0 收藏0
  • 93. Restore IP Addresses

    摘要:第一种解法,找出第一部分合法的剩余部分变成相似子问题。这里的特性是最大数字不能超过。比上个方法好的地方在于才会判断数字是否合法,避免了很多这种不需要检查的情况。 Given a string containing only digits, restore it by returning all possible valid IP address combinations. For e...

    andong777 评论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 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<