93. Restore IP Addresses

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);
        }
    }
}

原文 

https://segmentfault.com/a/1190000018144845

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 93. Restore IP Addresses

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址