93. Restore IP Addresses

andong777 發布于2019-08-14 17:59 / 1855人閱讀

摘要：第一種解法，找出第一部分合法的剩余部分變成相似子問題。這里的特性是最大數字不能超過。比上個方法好的地方在于才會判斷數字是否合法，避免了很多這種不需要檢查的情況。

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)

第一種解法，backtracking, 找出第一部分合法的IP, 剩余部分變成相似子問題。

public class Solution {
    public List restoreIpAddresses(String s) {
        List res = new ArrayList();
        if(s.length() < 4 || s.length() > 12) return res;
        dfs(s, "", res, 1);
        return res;
    }
    
    public void dfs(String s, String temp, List res, int count){
        if(count == 4 && isValid(s)){
            res.add(temp + s);
            return;
        }
        
        for(int i = 1; i < Math.min(4, s.length()); i++){
            String cur = s.substring(0, i);
            if(isValid(cur)){
                dfs(s.substring(i),  temp + cur + ".", res, count+1);
            }
        }
    }
    
    public boolean isValid(String s){
        if(s.charAt(0) == "0") return s.equals("0");
        int num = Integer.parseInt(s);
        return 0 < num && num < 256;
    }
}

2 這里IP的特性是最大數字不能超過255。比上個方法好的地方在于a+b+c+d= s.length()才會判斷數字是否合法，避免了很多1+1+1+N這種不需要檢查的情況。

public class Solution {
    public List restoreIpAddresses(String s) {
        List ret = new ArrayList<>();
        
        StringBuffer ip = new StringBuffer();
        for(int a = 1 ; a < 4 ; ++ a)
        for(int b = 1 ; b < 4 ; ++ b)
        for(int c = 1 ; c < 4 ; ++ c)
        for(int d = 1 ; d < 4 ; ++ d)
        {
            if(a + b + c + d == s.length() )
            {
                int n1 = Integer.parseInt(s.substring(0, a));
                int n2 = Integer.parseInt(s.substring(a, a+b));
                int n3 = Integer.parseInt(s.substring(a+b, a+b+c));
                int n4 = Integer.parseInt(s.substring(a+b+c));
                if(n1 <= 255 && n2 <= 255 && n3 <= 255 && n4 <= 255)
                {
                    ip.append(n1).append(".").append(n2)
                        .append(".").append(n3).append(".").append(n4);
                    if(ip.length() == s.length() + 3) ret.add(ip.toString());
                    ip.delete(0, ip.length());
                }
            }
        }
        return ret;
    }
}

GPU云服務器云服務器 Addresses Restore mac93云服務器軟件注冊表reg restore

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66922.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