1. question: 复原IP地址(中等) 有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔。
例如:”0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址,但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1 “ 是 无效 IP 地址。 给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能的有效 IP 地址,这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/restore-ip-addresses
示例 1:
1 2 输入:s = "25525511135" 输出:["255.255.11.135","255.255.111.35"]
示例 2:
1 2 输入:s = "0000" 输出:["0.0.0.0"]
示例 3:
1 2 输入:s = "101023" 输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示:
1 2 1 <= s.length <= 20 s 仅由数字组成
2. answers 这道题和分割回文串类似。只不过这道题限制了将字符串分割成4个子串。并且限制了每个子串的数值大小。主要有如下要求:
每个数字不能大于255,即限制了每个数字的长度最多为3位,即每个数字最多有三个选择。
每个数字不能以0开头。
4个数字必须将字符串完全用完。
所以,递归的终止条件是生成了4个数字,且字符串遍历完。代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 public class Solution_0084 { public List<String> result = new ArrayList<>(); public LinkedList<String> ip = new LinkedList<>(); public void generateIP (char [] chars, int startIndex) { if (ip.size() == 4 ) { if (startIndex == chars.length) { StringBuilder sbs = new StringBuilder(); for (String str: ip) { sbs.append(str).append("." ); } sbs.deleteCharAt(sbs.length() - 1 ); result.add(sbs.toString()); } return ; } int endIndex = Math.min(startIndex + 2 , chars.length - 1 ); StringBuilder sb = new StringBuilder(); for (int i = startIndex; i <= endIndex; i++) { sb.append(chars[i]); if (sb.length() > 1 && sb.charAt(0 ) == '0' ) return ; if (Integer.parseInt(sb.toString()) > 255 ) return ; ip.add(sb.toString()); generateIP(chars, i + 1 ); ip.removeLast(); } } public List<String> restoreIpAddresses (String s) { if (s.length() >= 4 ) generateIP(s.toCharArray(), 0 ); return result; } public static void main (String[] args) { String str = "1" ; Solution_0084 s = new Solution_0084(); List<String> strings = s.restoreIpAddresses(str); for (String strs: strings){ System.out.println(strs); } } }
3. 备注 参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com) ,代码随想录 (programmercarl.com) 。