<cite id="magsu"></cite>

LeetCode: 93. Restore IP Addresses

Shisui 發布于2019-08-14 14:28 / 1513人閱讀

摘要：以剩下的字符串，當前字符串，剩余單元數傳入下一次遞歸。結束條件字符串長度為，并且剩余單元數為

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;
    }
}

云服務器 GPU云服務器 Addresses Restore mac93云服務器軟件 LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65030.html

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
93. Restore IP Addresses

摘要：第一種解法，找出第一部分合法的剩余部分變成相似子問題。這里的特性是最大數字不能超過。比上個方法好的地方在于才會判斷數字是否合法，避免了很多這種不需要檢查的情況。 Given a string containing only digits, restore it by returning all possible valid IP address combinations. For e...

andong777 2019-08-14 17:59 評論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