LeetCode_回溯_中等_93.复原 IP 地址

这篇具有很好参考价值的文章主要介绍了LeetCode_回溯_中等_93.复原 IP 地址。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.题目

有效 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 中的任何数字。你可以按任何顺序返回答案。

示例 1:
输入:s = “25525511135”
输出:[“255.255.11.135”,“255.255.111.35”]

示例 2:
输入:s = “0000”
输出:[“0.0.0.0”]

示例 3:
输入:s = “101023”
输出:[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

提示:
1 <= s.length <= 20
s 仅由数字组成

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/restore-ip-addresses

2.思路

(1)回溯
思路参考本题官方题解。

相关题目:
LeetCode_字符串_中等_468.验证 IP 地址文章来源地址https://www.toymoban.com/news/detail-431232.html

3.代码实现(Java)

//思路1————回溯
class Solution {

    static final int SEG_COUNT = 4;
    List<String> res = new ArrayList<>();
    int[] segments = new int[SEG_COUNT];

    public List<String> restoreIpAddresses(String s) {
        backtrack(s, 0, 0);
        return res;
    }

    public void backtrack(String s, int segId, int segStart) {
        //如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
        if (segId == SEG_COUNT) {
            if (segStart == s.length()) {
                StringBuilder builder = new StringBuilder();
                for (int i = 0; i < SEG_COUNT; i++) {
                    builder.append(segments[i]);
                    if (i != SEG_COUNT - 1) {
                        builder.append('.');
                    }
                }
                res.add(builder.toString());
            }
            return;
        }
        //如果还没有找到 4 段 IP 地址就已经遍历完了字符串,那么提前回溯
        if (segStart == s.length()) {
            return;
        }
        //由于不能有前导零,如果当前数字为 0,那么这一段 IP 地址只能为 0
        if (s.charAt(segStart) == '0') {
            segments[segId] = 0;
            backtrack(s, segId + 1, segStart + 1);
        }
        //一般情况,枚举每一种可能性并递归
        int addr = 0;
        for (int segEnd = segStart; segEnd < s.length(); segEnd++) {
            addr = addr * 10 + (s.charAt(segEnd) - '0');
            if (addr > 0 && addr <= 255) {
                segments[segId] = addr;
                backtrack(s, segId + 1, segEnd + 1);
            } else {
                break;
            }
        }
    }
}

到了这里,关于LeetCode_回溯_中等_93.复原 IP 地址的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣 93. 复原 IP 地址

    题目来源:https://leetcode.cn/problems/restore-ip-addresses/description/ C++题解:递归回溯法。 递归参数:因为不能重复分割,需要ind记录下一层递归分割的起始位置;还需要一个变量num,记录ip段的数量。 递归终止条件:ip段的数量达到4 且 ind等于s的长度,可进行有效ip地址保存;当

    2024年02月12日
    浏览(38)
  • 力扣每日一题93:复原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 地址。 给定一个只包含数字的字

    2024年02月06日
    浏览(35)
  • 代码随想录23| 93.复原IP地址, 78.子集, 90.子集II

    题目链接/文章讲解:链接地址 视频讲解:链接地址 题目链接/文章讲解:链接地址 视频讲解:链接地址 题目链接/文章讲解:链接地址 视频讲解:链接地址

    2024年02月11日
    浏览(87)
  • 代码随想录刷题笔记 DAY 28 | 复原 IP 地址 No.93 | 子集 No.78 | 子集 II No.90

    01. 复原 IP 地址(No. 93) 题目链接 代码随想录题解 1.1 题目 有效 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\\\" 是 无效 I

    2024年02月22日
    浏览(46)
  • LeetCode 1079. Letter Tile Possibilities【哈希表,回溯,动态规划,排列组合】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月10日
    浏览(50)
  • 面试热题(复原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 地址。 给定一个只包含数字的字

    2024年02月11日
    浏览(46)
  • 算法刷题Day 28 复原IP地址+子集+子集II

    我的做法有点奇怪,还是参考一下代码随想录的做法吧 涉及到去重,可别忘了排序 不然去重的效果没法实现

    2024年02月16日
    浏览(41)
  • Rust每日一练(Leetday0031) 解码方法、复原 IP 地址

    目录 91. 解码方法  Decode Ways  🌟🌟 93. 复原 IP 地址 Restore IP Addresses  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 一条包含字母  A-Z  的消息通过以下映射进行了  编码  : 要  解码  已编码的消息,所有

    2024年02月09日
    浏览(35)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集

    一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。 1、基本思想: 从问题的起

    2024年02月11日
    浏览(42)
  • 【刷题笔记8.10】LeetCode题目:有效括号

    给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号 首先,解决此题,我们要明确使用 栈

    2024年02月13日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包