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"]
class Solution { public ListrestoreIpAddresses(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); } } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/72656.html
摘要:以剩下的字符串,當前字符串,剩余單元數傳入下一次遞歸。結束條件字符串長度為,并且剩余單元數為 Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example:Given 25525511135, return [2...
摘要:題目要求返回字符串能夠組成的所有地址。思路與代碼地址由位二進制數字構成,一共分為個區間,每個區間位。那么我們只要劃分出這四個區間,然后判斷這四個區間的值是否符合標準即可。 題目要求 Given a string containing only digits, restore it by returning all possible valid IP address combinatio...
摘要:題目描述題目理解將一段字符廣度搜索截取,分別有種組合形式,添加限制條件,過濾掉不適合的組合元素。長度,大小,首字母應用如果進行字符串的子元素組合窮舉,可以應用。所有的循環,利用到前一個狀態,都可以理解為動態規劃的一種分支 題目描述:Given a string containing only digits, restore it by returning all possible va...
摘要:第一種解法,找出第一部分合法的剩余部分變成相似子問題。這里的特性是最大數字不能超過。比上個方法好的地方在于才會判斷數字是否合法,避免了很多這種不需要檢查的情況。 Given a string containing only digits, restore it by returning all possible valid IP address combinations. For e...
摘要:第一個分割點第二個分割點第三個分割點 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....
閱讀 1164·2021-11-22 15:24
閱讀 4440·2021-09-23 11:51
閱讀 2302·2021-09-08 09:36
閱讀 3514·2019-08-30 15:43
閱讀 1295·2019-08-30 13:01
閱讀 1116·2019-08-30 12:48
閱讀 530·2019-08-29 12:52
閱讀 3366·2019-08-29 12:41