[LeetCode] 93. Restore IP Addresses

xingqiba 發(fā)布于2019-08-16 13:58 / 1727人閱讀

Problem

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Solution

class Solution {
    public List restoreIpAddresses(String s) {
        //4 segments, 0-255, dfs from 0 to len-1
        List res = new ArrayList<>();
        dfs(s, 0, 0, "", res);
        return res;
    }
    private void dfs(String str, int index, int count, String temp, List res) {
        int n = str.length();
        if (count == 4 && index == n) {
            res.add(temp);
            return;
        }
        if (count > 4 || index > n) return;
        for (int i = 1; i <= 3; i++) {
            if (index+i > n) break;
            String part = str.substring(index, index+i);
            if (part.startsWith("0") && part.length() != 1 ||
               Integer.parseInt(part) > 255) continue;
            String cur = temp+part;
            if (count != 3) cur += ".";
            dfs(str, index+i, count+1, cur, res);
        }
    }
}

GPU云服務(wù)器云服務(wù)器 Addresses Restore mac93云服務(wù)器軟件 LeetCode

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/72656.html

相關(guān)文章

LeetCode: 93. Restore IP Addresses

摘要：以剩下的字符串，當(dāng)前字符串，剩余單元數(shù)傳入下一次遞歸。結(jié)束條件字符串長(zhǎng)度為，并且剩余單元數(shù)為 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 評(píng)論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 2019-08-15 10:55 評(píng)論0 收藏0
leetcode-93-Restore IP Addresses

摘要：題目描述題目理解將一段字符廣度搜索截取，分別有種組合形式，添加限制條件，過濾掉不適合的組合元素。長(zhǎng)度，大小，首字母應(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 2019-07-31 11:11 評(píng)論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 2019-08-14 17:59 評(píng)論0 收藏0
[LintCode/LeetCode] Restore IP Addresses

摘要：第一個(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....

bingo 2019-08-14 15:14 評(píng)論0 收藏0