資訊專欄INFORMATION COLUMN
摘要：第一種解法，找出第一部分合法的剩余部分變成相似子問題。這里的特性是最大數(shù)字不能超過。比上個(gè)方法好的地方在于才會(huì)判斷數(shù)字是否合法，避免了很多這種不需要檢查的情況。
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的特性是最大數(shù)字不能超過255。比上個(gè)方法好的地方在于a+b+c+d= s.length()才會(huì)判斷數(shù)字是否合法，避免了很多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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66922.html
摘要：以剩下的字符串，當(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...
摘要：題目要求返回字符串能夠組成的所有地址。思路與代碼地址由位二進(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...
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...
摘要：題目描述題目理解將一段字符廣度搜索截取，分別有種組合形式，添加限制條件，過濾掉不適合的組合元素。長度，大小，首字母應(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...
摘要：第一個(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....
閱讀 1215·2021-11-23 09:51
閱讀 1993·2021-10-08 10:05
閱讀 2352·2019-08-30 15:56
閱讀 1911·2019-08-30 15:55
閱讀 2645·2019-08-30 15:55
閱讀 2498·2019-08-30 13:53
閱讀 3510·2019-08-30 12:52
閱讀 1259·2019-08-29 10:57
