LeetCode93 : Restore IP Addresses

Description

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"]

解题思路

第一步:明确 IP (IPv4) 地址的定义:
(0 ~ 255).(0 ~ 255).(0 ~ 255).(0 ~ 255), 合法的 IP 地址在 相邻两个点之间要么只能存在一个 0 ,要么只能以非 0 数字开头。

第二步:进行深度遍历,下面贴出代码的操作图

这里面 k 表示每一个分割区间有几个数字。

代码实现

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null) {
            return res;
        }
        if (s.length() < 4 || s.length() > 12) {
            return res;
        }
        helper(res, 0, s,"");
        return res;
    }
    private void helper(List<String> res, int pos, String s, String temp) {
        if (pos == 4) {
            if (s.length() == 0) {
                res.add(temp.substring(0, temp.length() - 1));
            }
            return ;
        }
        for (int k = 1; k <= 3; ++ k) {
            if (s.length() < k) {
                continue;
            }
            int val = Integer.parseInt(s.substring(0, k));
            if (val > 255 || k != String.valueOf(val).length()) {
                continue;
            }
            helper( res, pos + 1, s.substring(k), temp + s.substring(0, k) + ".");
        }
    }
}

代码解释

 if (val > 255 || k != String.valueOf(val).length()) {
            continue;
  }

|| 运算后面的是为了防止出现 1.01.0.1 这种情况,因为 01 是不合法的。这里还涉及到一个小知识点: 以 0 开头的数字在 Java 编码中代表的是 八进制。例:

 int val(十进制) = 022(八进制);

这个 val 打印出来的值是 18. Java 会自动进行进制转换

说点什么

avatar
  Subscribe  
提醒

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部