LogicStack-LeetCode 刷穿系列｜1108. IP 地址无效化：基于单遍扫描的字符串「模拟」解法

教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇是「宫水三叶的刷题日记」刷穿 LeetCode 系列第 No.1108 篇题解的深度展开聚焦 LeetCode 1108「IP 地址无效化」这一道难度为简单、Tag 为「模拟」的字符串处理题。文章将以 LeetCode/1101-1110/1108. IP 地址无效化简单.md 为骨架完整讲解题意、模拟思路与 Java 实现并补充 C/Python/TypeScript 等价写法、复杂度分析与同类题目对照帮助你真正掌握「字符串逐字符扫描 结果构建」这一类模拟题的通用解法。题目描述与题意理解原题背景这是 LeetCode 上的1108. IP 地址无效化难度简单Tag 为「模拟」。题目定义给你一个有效的IPv4地址address返回这个IP地址的无效化版本。所谓无效化IP地址其实就是用[.]代替了每个.。题目给出的唯一提示是给出的address是一个有效的IPv4地址。这意味着输入无需再做格式校验例如不需要判断段位是否在0~255、是否有前导零等直接把注意力集中在「替换点号」这一个动作上即可这正是模拟题「把规则翻译成代码」的典型形态。示例拆解示例 1输入address 1.1.1.1 输出1[.]1[.]1[.]1输入是1.1.1.1其中包含 3 个.逐一替换为[.]后得到1[.]1[.]1[.]1。注意原字符串长度为 7替换后长度变为7 3×2 13每个.由 1 个字符膨胀为 3 个字符净增 2 个字符。示例 2输入address 255.100.50.0 输出255[.]100[.]50[.]0输入255.100.50.0同样是 3 个点号替换后各段数字保持不变仅点号被包裹进方括号。这两个示例足以覆盖题目的全部行为非点号字符原样保留点号字符被[.]整体替换。思路分析为什么这是一道「模拟」题「模拟」是算法题中非常常见的一类题目本身不要求你设计精巧的数据结构或复杂的推导而是把现实生活中或题目设定的规则里的某个过程用代码一步一步「照着做」。本题的规则只有一条——遇到.就替换成[.]其余字符照抄因此完全符合模拟题的特征。在 Index/模拟.md 这份模拟类题目的总索引中本题与 1678. 设计 Goal 解析器简单、1047. 删除字符串中的所有相邻重复项简单、1410. HTML 实体解析器中等 等一同被归类为「字符串模拟」的范畴。它们的共同点是输入规模小本题目未给出显式长度上限但依据有效的 IPv4 地址定义输入最长不超过 15 个字符255.255.255.255O(n) 与 O(n²) 的差异在此规模下几乎无感规则确定、无分支博弈不存在贪心选择或状态转移每一步如何处理完全由当前字符决定结果是一个新串需要在遍历过程中持续「构建」输出字符串。对比同目录下的其他题目可见1104. 二叉树寻路 与 1106. 解析布尔表达式 分别考察「模拟 数学找规律」与「模拟 栈」而本题只考察最纯粹的字符替换模拟是入门模拟类问题的最佳例题之一。模拟解法单遍扫描 结果构建算法流程根据题意进行模拟即可核心步骤只有三步从左到右遍历输入字符串s的每一个字符若当前字符不是.直接将其追加到结果字符串若当前字符是.改为追加[.]这一整体先追加[再追加.最后追加]。Java 实现原题解代码原文档给出的 Java 代码如下这里补充了逐行注释便于理解class Solution { public String defangIPaddr(String s) { StringBuilder sb new StringBuilder(); // 结果构建器 int n s.length(), idx -1; // n输入长度idx 从 -1 起 while (idx n) { // 每次进入循环前先自增等价于 for (idx 0; idx n; idx) char c s.charAt(idx); // 取出当前字符 if (c .) sb.append([); // 遇到点号先补左括号 sb.append(c); // 无论如何都追加当前字符点号也会被追加进来 if (c .) sb.append(]); // 遇到点号再补右括号 } return sb.toString(); // 返回构建完成的字符串 } }这段代码的巧妙之处在于没有使用「遇到.则跳过并追加[.]」的分支写法而是用「前后各补一个括号」的方式让.字符本身仍然被追加进结果从而把[、.、]三个字符拼接到位。这样代码中唯一的判断条件仍然是c .逻辑非常紧凑。等价的多语言实现原题解以 Java 给出这里依据完全相同的「逐字符扫描 结果构建」思路整理出其余常用语言的等价实现可直接在对应语言环境中运行验证Cclass Solution { public: string defangIPaddr(string s) { string ans; for (char c : s) { if (c .) ans [.]; else ans c; } return ans; } };Pythonclass Solution: def defangIPaddr(self, address: str) - str: ans [] for c in address: if c .: ans.append([.]) else: ans.append(c) return .join(ans)TypeScriptfunction defangIPaddr(address: string): string { let ans for (const c of address) { if (c .) ans [.] else ans c } return ans }说明以上多语言版本均为依据原题解「模拟」思路整理出的等价实现仓库本体以 Markdown 题解文档为主体例如 README.md 所述这是一个「日更」的题解仓库其中并不包含独立的源代码文件提交时请以各语言平台的语法为准。正确性论证与边界情况无点号输入例如输入1或12循环中不会触发任何一次.分支结果与输入完全一致符合「无效化版本」的语义多连续点号IPv4 规范中不允许连续点号如1..1不是有效地址题目已保证输入有效因此无需考虑该情况但即使出现上述逻辑也会把每个.独立替换为[.]行为依然确定点号位于首尾有效 IPv4 地址不会以.开头或结尾不过即便出现逻辑同样正确处理因为算法不依赖点号的位置空串有效 IPv4 地址非空但若传入空串while循环一次都不进入直接返回空串代码同样健壮。复杂度分析时间复杂度O(n)。其中 n 为输入字符串长度。整个算法只对输入做一遍扫描每次字符操作追加都是常数时间因此总耗时与输入规模线性相关。空间复杂度O(n)。结果字符串的长度为n 2×kk 为点号个数每个点号由 1 个字符膨胀为 3 个字符因此构建结果所需的空间与输入长度同阶。若把返回结果本身不计入额外空间则辅助空间为 O(1)。从本题延伸字符串「构建」的性能细节为什么使用 StringBuilder 而非 String 拼接在 Java 中String是不可变对象str c每次拼接都会创建新的字符串对象。虽然现代 JVM 与编译器会在简单场景下做优化但在循环体内反复拼接时显式使用StringBuilder仍是更稳妥、可控的做法——这正是原题解使用StringBuilder的原因。同理Python 版本优先使用list收集字符再.join(ans)而不是在循环里做ans c的字符串累加也是为了避免产生大量中间字符串。为什么不直接调用 replaceString.replace(., [.])一行也能完成替换且同样是线性复杂度。原题解选择手写循环的价值在于可读性与教学性展示模拟题「逐字符处理」的通用框架这个框架可以直接迁移到 1410. HTML 实体解析器需要识别quot;、amp;等多字符实体或 1678. 设计 Goal 解析器需要按G、()、(al)分段解释这类「多模式匹配」的字符串模拟题上控制力更强当替换规则从「单字符 → 固定串」升级为「多字符 → 变长串」时手写扫描仍然成立而简单的replace可能引入重叠匹配等隐患。扩展到「多模式替换」的通用框架把本题的扫描框架稍作泛化就得到字符串模拟题的通用骨架初始化结果容器 while (未遍历完输入) { 判断当前位置是否命中某条替换规则 命中追加替换结果指针按规则长度前进 未命中追加原字符指针前进 1 } 返回结果HTML 实体解析器 正是这个框架的进阶版它以为触发点向后最多读取 6 个字符在哈希表中查找匹配的实体再替换时间复杂度为 O(n×6)与本题的 O(n) 一脉相承。建议将这两道题放在一起练习可以完整覆盖「简单替换」到「实体解析」的模拟能力梯度。小结与仓库导航1108. IP 地址无效化是一道教科书级的「模拟」入门题规则单一、无陷阱、无优化难点核心价值在于帮助建立「读题 → 翻译规则 → 逐字符模拟 → 构建结果」的解题习惯。本题的标准解法时间复杂度为 O(n)空间复杂度为 O(n)。如果你想继续系统性地刷「模拟」类题目可以从仓库的 Index/模拟.md 索引表入手按推荐指数由高到低展开也可以直接浏览 LeetCode/1101-1110/ 目录与本题同区间还收录了 1104. 二叉树寻路中等、1106. 解析布尔表达式困难、1109. 航班预订统计中等 等不同难度的模拟类题解。这套题解系列从 2021/01/01 开始日更目标是逐步刷完当时 LeetCode 上所有不带锁的题目每一篇都力求给出最简洁的代码与清晰的思路讲解。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LeetCode-Go 题解 1108Defanging an IP Address —— Go 实现 IP 地址无效化. 转 [.]LeetCode Go 题解 1108Defanging an IP Address —— Go 实现 IP 地址无效化. 转 . 本篇基于示例工程字符串哈希全解从滚动哈希原理到 LeetCode 重复子串/连接词/字符串轮转实战LogicStack-LeetCode 刷穿系列字符串哈希全解从滚动哈希原理到 LeetCode 重复子串/连接词/字符串轮转实战LogicStack LeetCode 刷穿系列 字符串哈希Strin教程文档安装 .NET SDK 完整指南dotnet SDK 10 LTS 一次装对的四条路线安装 .NET SDK 完整指南dotnet SDK 10 LTS 一次装对的四条路线 给新机器安装 .NET SDK最容易翻车的是选错包、选错版本、漏装系教程文档上一篇ramsey/uuid 全局辅助函数 v1–v8 全解析一行代码直接生成 UUID 字符串下一篇PaddleHub 版本演进与技术能力全景解读从 v0.5.0 到 v2.3.0 的发布历史创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考