问题描述:
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)
原问题链接:https://leetcode.com/problems/restore-ip-addresses/
问题分析
在这个问题描述里,主要针对的是ipv4的值的情况。从给定的字符串来说,一个ip地址所对应的地址分为4个字段,每个字段对应的数值最多为3位。假定我们先考虑地址的第一个部分,那么它可以取的值为0到255之间。所以它在对应的字符串里可以取第一个字符,第一二个字符和第一到第三个字符的情况。它们对应于字符串里的子串(s.charAt(0, 1), s.charAt(0, 2), s.charAt(0, 3))。这些情况里我们还需要判断它最终解析成整数的值是否在255之内。
这样,对于取ip地址的第一段来说,我们只需要循环的取前面的1, 2, 3这几个字符的情况来判断就可以了。对于后面的第二、三四段来说也类似。每次在前一个的基础上取1, 2, 3这几个字符,然后再来判断。如果合格的,就将构造出来的串加入到结果列表中。
按照这个思路,详细的代码实现如下:
public class Solution { public List<String> restoreIpAddresses(String s) { List<String> list = new ArrayList<String>(); int len = s.length(); for(int i = 1; i < 4 && i < len - 2; i++) { for(int j = i + 1; j < i + 4 && j < len - 1; j++) { for(int k = j + 1; k < j + 4 && k < len; k++) { String s1 = s.substring(0, i); String s2 = s.substring(i, j); String s3 = s.substring(j, k); String s4 = s.substring(k, len); if(isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) list.add(s1 + "." + s2 + "." + s3 + "." + s4); } } } return list; } public boolean isValid(String s){ if(s.length() > 3 || s.length() == 0 || (s.charAt(0) == '0' && s.length() > 1) || Integer.parseInt(s) > 255) return false; return true; } }
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
Leetcode:Leetcode提交
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
LeetCode 101:和你一起你轻松刷题(C++)
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码
LeetCode:LeetCode的注释
leetcode:LeetCode问题
leetcode:LeetCode题解
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...