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); } } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/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....
阅读 1138·2021-11-22 15:24
阅读 4334·2021-09-23 11:51
阅读 2264·2021-09-08 09:36
阅读 3492·2019-08-30 15:43
阅读 1279·2019-08-30 13:01
阅读 1097·2019-08-30 12:48
阅读 505·2019-08-29 12:52
阅读 3303·2019-08-29 12:41