算法leetcode|93. 复原 IP 地址(多语言实现)

这篇具有很好参考价值的文章主要介绍了算法leetcode|93. 复原 IP 地址(多语言实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。



93. 复原 IP 地址:

有效 IP 地址 正好由四个整数(每个整数位于 0255 之间组成,且不能含有前导 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 仅由数字组成

分析:

  • 面对这道算法题目,二当家的再次陷入了沉思。
  • ip地址大家都是知道的,ipv4是由4段组成,每段的取值范围都是 [0,255]。
  • 给出一个ip地址我们都可以判断出是否合法有效,但是现在相当于是反向构建合法有效的ip地址,所以我们就是看字符串有多少种合法ipv4的拆分可能。
  • 按照顺序,4段中的每段都可以是1位到3位10进制数,但是不可以有前导0,取值范围是 [0,255]。
  • 去尝试所有的可能,看是否恰好拆分成4段有效值,即正好所有的字符都使用了,并且拆分成了4段有效值。
  • 祭出深度优先,非常强大的递归套娃大法,更准确地说是回溯算法。
  • 注:回溯算法一般需要一个数据结构存储一个临时状态,需要在回溯时还原状态。

题解:

rust:

impl Solution {
    pub fn restore_ip_addresses(s: String) -> Vec<String> {
        fn dfs(s: &str, ans: &mut Vec<String>, segments: &mut Vec<String>, seg_start: usize) {
            // 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
            if 4 == segments.len() {
                if seg_start == s.len() {
                    ans.push(segments.join("."));
                }
                return;
            }

            // 一般情况,枚举每一种可能性并递归
            for seg_end in seg_start + 1..=s.len() {
                let segment = &s[seg_start..seg_end];
                if (segment.starts_with('0') && (seg_end - seg_start) > 1) || segment.parse::<usize>().unwrap() > 0xFF {
                    // 有前导零 或者 地址范围大于255
                    break;
                }
                segments.push(segment.to_string());
                dfs(s, ans, segments, seg_end);
                segments.pop();
            }
        }

        let mut ans = Vec::new();

        dfs(s.as_str(), &mut ans, &mut Vec::new(), 0);

        return ans;
    }
}

go:

func restoreIpAddresses(s string) []string {
    var ans []string

	var dfs func([]string, int)
	dfs = func(segments []string, segStart int) {
		// 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
		if 4 == len(segments) {
			if segStart == len(s) {
				ans = append(ans, strings.Join(segments, "."))
			}
			return
		}

		// 一般情况,枚举每一种可能性并递归
		for segEnd := segStart + 1; segEnd <= len(s); segEnd++ {
			segment := s[segStart:segEnd]
			addr, _ := strconv.ParseInt(segment, 10, 0)
			if (segment[0] == '0' && (segEnd-segStart) > 1) || addr > 0xFF {
				// 有前导零 或者 地址范围大于255
				break
			}
			dfs(append(segments, segment), segEnd)
		}
	}

	dfs([]string{}, 0)

	return ans
}

c++:

class Solution {
private:
    void dfs(const string& s, vector<string>& ans, string segments[], int segIdx, int segStart) {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
        if (4 == segIdx) {
            if (segStart == s.size()) {
                string addr;
                for (int i = 0; i < 4; ++i) {
                    addr += segments[i];
                    if (i != 3) {
                        addr += '.';
                    }
                }
                ans.emplace_back(addr);
            }
            return;
        }

        // 一般情况,枚举每一种可能性并递归
        for (int segEnd = segStart + 1; segEnd <= s.size(); ++segEnd) {
            string segment = s.substr(segStart, segEnd - segStart);
            if ((segment[0] == '0' && (segEnd - segStart) > 1) || stoi(segment) > 0xFF) {
                // 有前导零 或者 地址范围大于255
                break;
            }
            segments[segIdx] = segment;
            dfs(s, ans, segments, segIdx + 1, segEnd);
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ans;
        string segments[4];
        dfs(s, ans, segments, 0, 0);
        return ans;
    }
};

python:

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        ans = list()

        def dfs(segments: List[str], seg_start: int):
            # 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
            if 4 == len(segments):
                if seg_start == len(s):
                    ans.append(".".join(segments))
                return

            # 一般情况,枚举每一种可能性并递归
            for seg_end in range(seg_start + 1, len(s) + 1):
                segment = s[seg_start:seg_end]
                if (segment[0] == '0' and (seg_end - seg_start) > 1) or int(segment) > 0xFF:
                    # 有前导零 或者 地址范围大于255
                    break
                segments.append(segment)
                dfs(segments, seg_end)
                segments.pop()

        dfs(list(), 0)
        return ans


java:

class Solution {
    public List<String> restoreIpAddresses(String s) {
        final List<String> ans = new ArrayList<>();
        dfs(s, ans, new String[4], 0, 0);
        return ans;
    }

    private void dfs(String s, List<String> ans, String[] segments, int segIdx, int segStart) {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
        if (4 == segIdx) {
            if (segStart == s.length()) {
                ans.add(String.join(".", segments));
            }
            return;
        }

        // 一般情况,枚举每一种可能性并递归
        for (int segEnd = segStart + 1; segEnd <= s.length(); ++segEnd) {
            String segment = s.substring(segStart, segEnd);
            if ((segment.charAt(0) == '0' && (segEnd - segStart) > 1) || Integer.parseInt(segment) > 0xFF) {
                // 有前导零 或者 地址范围大于255
                break;
            }
            segments[segIdx] = segment;
            dfs(s, ans, segments, segIdx + 1, segEnd);
        }
    }
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~文章来源地址https://www.toymoban.com/news/detail-761863.html


到了这里,关于算法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日
    浏览(42)
  • 力扣每日一题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日
    浏览(37)
  • 代码随想录23| 93.复原IP地址, 78.子集, 90.子集II

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

    2024年02月11日
    浏览(91)
  • 代码随想录刷题笔记 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日
    浏览(50)
  • 算法leetcode|94. 二叉树的中序遍历(多语言实现)

    给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 树中节点数目在范围 [0, 100] 内 -100 = Node.val = 100 面对这道算法题目,二当家的再次陷入了沉思。 二叉树的中序遍历和前序遍历,后续遍历是二叉树常用的遍历方式。 使用递归方式比循环非递归方式更加简单,直观,易于

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

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

    2024年02月16日
    浏览(42)
  • 面试热题(复原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日
    浏览(48)
  • Rust每日一练(Leetday0031) 解码方法、复原 IP 地址

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

    2024年02月09日
    浏览(37)
  • 【算法与数据结构】232、LeetCode用栈实现队列

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :这道题要求我们用栈模拟队列(工作上一定没人这么搞)。程序当中,push函数很好解决,直接将元素push进输入栈当中。pop函数需要实现队列先进先出的操作,而栈是先进后出。只

    2024年02月12日
    浏览(44)
  • 【算法与数据结构】28、LeetCode实现strStr函数

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :首先判断字符串是否合法,然后利用for循环,取出子字符串利用compare函数进行比较。    程序如下 : 复杂度分析: 时间复杂度: O ( n ∗ m ) O(n * m) O ( n ∗ m ) ,假设haystack的长

    2024年02月12日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包