成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Restore IP Addresses

bingo / 3014人閱讀

摘要：第一個(gè)分割點(diǎn)第二個(gè)分割點(diǎn)第三個(gè)分割點(diǎn)

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.255.111.35"
]

Order does not matter.

Solution

Ordinary DFS Method

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

Advanced DFS Method

public class Solution {
    private List res;
    public List restoreIpAddresses(String s) {
        res = new ArrayList();
        String cur = "";
        dfs(s, cur, -1, 0);
        return res;
    }
    public void dfs(String s, String cur, int index, int len) {
        if (len == 4 && index == s.length()-1) {
            res.add(cur.substring(0, cur.length()-1));
            return;
        }
        int temp = 0;
        if (s.length()-1-index > 3*(4-len)) return;
        for (int i = 1; i <= 3; i++) {
            if (index+i >= s.length()) break;
            if (i == 1 && s.charAt(index+1) == "0") {
                dfs(s, cur+"0.", index+1, len+1);
                break;
            }
            temp = temp*10 + s.charAt(index+i)-"0";
            if (temp <= 255) dfs(s, cur + temp + ".", index+i, len+1);
        }
    }
}

Optimized Above DFS Method

public class Solution {
    public List restoreIpAddresses(String s) {
        List res = new ArrayList<>();
        dfs(s, 0, "", res);
        return res;
    }
    private void dfs(String s, int index, String cur, List res) {
        if (index == 4) res.add(cur.substring(0, cur.length() - 1));
        else {
            for (int i = 0; i < 3; i++) {
                if (s.length() - i - 1 < 3 - index || s.length() - i - 1 > (3 - index) * 3) continue;
                if (i > 0 && s.charAt(0) == "0") break;
                if (i == 2 && s.substring(0, 3).compareTo("255") > 0) break;
                dfs(s.substring(i + 1), index + 1, cur + s.substring(0, i + 1) + ".", res);
            }
        }
    }
}

A simple way... O(n^3)

public class Solution {
    public List restoreIpAddresses(String s) {
        List res = new LinkedList();
        int len = s.length();
        // 第一個(gè)分割點(diǎn)
        for(int i = 1; i < 4 && i < len - 2; i++){
            // 第二個(gè)分割點(diǎn)
            for(int j = i + 1; j < i + 4 && j < len - 1; j++){
                // 第三個(gè)分割點(diǎn)
                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"));
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65470.html

相關(guān)文章

  • LeetCode: 93. Restore IP Addresses

    摘要：以剩下的字符串，當(dāng)前字符串，剩余單元數(shù)傳入下一次遞歸。結(jié)束條件字符串長度為，并且剩余單元數(shù)為 Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example:Given 25525511135, return [2...

    Shisui 評論0 收藏0

  • 93. Restore IP Addresses

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

    andong777 評論0 收藏0

  • leetcode93. Restore IP Addresses

    摘要：題目要求返回字符串能夠組成的所有地址。思路與代碼地址由位二進(jìn)制數(shù)字構(gòu)成，一共分為個(gè)區(qū)間，每個(gè)區(qū)間位。那么我們只要?jiǎng)澐殖鲞@四個(gè)區(qū)間，然后判斷這四個(gè)區(qū)間的值是否符合標(biāo)準(zhǔn)即可。 題目要求 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

    摘要：題目描述題目理解將一段字符廣度搜索截取，分別有種組合形式，添加限制條件，過濾掉不適合的組合元素。長度，大小，首字母應(yīng)用如果進(jìn)行字符串的子元素組合窮舉，可以應(yīng)用。所有的循環(huán)，利用到前一個(gè)狀態(tài)，都可以理解為動(dòng)態(tài)規(guī)劃的一種分支 題目描述：Given a string containing only digits, restore it by returning all possible va...

    wmui 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<