前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 题目解析之 Restore IP Addresses

Leetcode 题目解析之 Restore IP Addresses

原创
作者头像
ruochen
发布2022-02-13 15:23:19
1.6K0
发布2022-02-13 15:23:19
举报
文章被收录于专栏:若尘的技术专栏

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)

代码语言:javascript
复制
    List<String> rt = new ArrayList<String>();
    String[] stack = new String[4];
    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() == 0) {
            return new ArrayList<String>();
        }
        dfs(s, 0, 0);
        return rt;
    }
    /**
     * 
     * @param s
     * @param p
     *            :指针
     * @param pstack
     *            :stack的下标
     */
    public void dfs(String s, int p, int pstack) {
        if (pstack == 4) {
            // 如果stack长度为4,且s的字符全部用上
            // 则stack[0...3]存了一个结果
            if (p >= s.length()) {
                String ip = String.join(".", stack);
                rt.add(ip);
            }
            return;
        }
        // 获取1~3个字符
        for (int i = 1; i <= 3; i++) {
            // 如果超过字符串长度,返回
            if (p + i > s.length()) {
                return;
            }
            // 若选取的第一个字符是0,则停止选取
            if (i > 1 && s.charAt(p) == '0') {
                continue;
            }
            String number = s.substring(p, p + i);
            // 如果number<=255,递归
            if (Integer.parseInt(number) <= 255) {
                stack[pstack] = number;
                dfs(s, p + i, pstack + 1);
            }
        }
    }

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档