内容简介:Given a string containing only digits, restore it by returning all possible valid IP address combinations.Example:难度:medium
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"]
难度:medium
题目:给定一字符串仅包含数字,恢复该字符串为所有可能合法的IP地址组合。
思路:递归
Runtime: 2 ms, faster than 91.11% of Java online submissions for Restore IP Addresses.
Memory Usage: 34.8 MB, less than 0.90% of Java online submissions for Restore IP Addresses.
class Solution { public List<String> restoreIpAddresses(String s) { List<String> result = new ArrayList(); if (null == s || s.length() < 4 || s.length() > 12) { return result; } restoreIpAddresses(s, 0, 0, "", result); return result; } private void restoreIpAddresses(String s, int i, int cnt, String str, List<String> result) { int sLength = s.length(); if (i >= sLength && cnt >= 4) { result.add(str.substring(0, str.length() - 1)); return; } int i1 = (i + 1) <= sLength ? Integer.parseInt(s.substring(i, i + 1)) : -1; if (i1 >= 0 && cnt < 4) { restoreIpAddresses(s, i + 1, cnt + 1, str + i1 + ".", result); } int i2 = (i + 2) <= sLength ? Integer.parseInt(s.substring(i, i + 2)) : -1; if (i2 >= 10 && i2 <= 99 && cnt < 4) { restoreIpAddresses(s, i + 2, cnt + 1, str + i2 + ".", result); } int i3 = (i + 3) <= sLength ? Integer.parseInt(s.substring(i, i + 3)) : -1; if (i3 >= 100 && i3 <= 255 && cnt < 4) { restoreIpAddresses(s, i + 3, cnt + 1, str + i3 + ".", result); } } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。