摘要:以剩下的字符串,当前字符串,剩余单元数传入下一次递归。结束条件字符串长度为,并且剩余单元数为
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)
给一串数字字符串,返回所有可能的合理ip地址
首先分析一个合理的ip地址包含几个条件:
有四个部分,每个部分以 . 隔开
每个部分最大为255,最小为0
每个部分最长3位
可以得到几个限制:
给定字符串只包含数字
给定字符串最长为12,最短为4
每个部分最大255,最小为0
每个部分最长3位,0开头则只能为1位
算法分析:
总数4个单元,从传入字符串中每次截取开头1到最长3个字符(长度不超过当前字符串长度)作为当前单元,忽略不符合限制的数字,加入到当前得到的ip字符串。以剩下的字符串,当前ip字符串,剩余单元数传入下一次递归。
结束条件:
字符串长度为0,并且剩余单元数为0
public class Solution { public ListrestoreIpAddresses(String s) { List res = new ArrayList<>(); if (s == null || s.length() == 0) { return res; } helper(s, "", 4, res); return res; } public void helper(String input, String cur, int partNum, List res) { if (input == null) { return; } if (input.length() > partNum * 3 || input.length() < partNum) { return; } if (input.length() == 0 && partNum == 0) { res.add(cur); return; } for (int i = 1; i <= 3 && i <= input.length(); i++) { String curTemp = input.substring(0,i); String rest = input.substring(i); if (isValid(curTemp)) { String temp = new String(cur); temp += curTemp; if (partNum > 1) { temp += "."; } helper(rest, temp, partNum-1, res); } } } public boolean isValid(String s) { if (s.charAt(0) == "0") { return s.equals("0"); } int temp = Integer.parseInt(s); return temp > 0 && temp <= 255; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65030.html
摘要:题目要求返回字符串能够组成的所有地址。思路与代码地址由位二进制数字构成,一共分为个区间,每个区间位。那么我们只要划分出这四个区间,然后判断这四个区间的值是否符合标准即可。 题目要求 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...
摘要:题目描述题目理解将一段字符广度搜索截取,分别有种组合形式,添加限制条件,过滤掉不适合的组合元素。长度,大小,首字母应用如果进行字符串的子元素组合穷举,可以应用。所有的循环,利用到前一个状态,都可以理解为动态规划的一种分支 题目描述: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....
阅读 825·2023-04-26 00:13
阅读 2794·2021-11-23 10:08
阅读 2432·2021-09-01 10:41
阅读 2112·2021-08-27 16:25
阅读 4177·2021-07-30 15:14
阅读 2359·2019-08-30 15:54
阅读 857·2019-08-29 16:22
阅读 2736·2019-08-26 12:13