IP 地址无效化 图解题解
这道题到底在问什么
- 输入
- address = "1.1.1.1"
- 输出
- "1[.]1[.]1[.]1"
- 输入
- 本节演示 address = "100.2.30.4"
- 输出
- "100[.]2[.]30[.]4"
先想最直接的笨办法
上面这一排是地址 "100.2.30.4" 拆开的 10 个字符,数字和小数点夹在一起。开扫之前先准备一个空的结果串,等会儿每看一个字符就往里添东西。从最左边第 0 个字符开始,一个一个往右看。（动画第 4 步）
最优解：一步一步想明白
- 3记牢两句话:是小数点就写成 "[.]",不是小数点就原样照抄。下面每一帧都在套这两句。
- 4上面这一排是地址 "100.2.30.4" 拆开的 10 个字符,数字和小数点夹在一起。开扫之前先准备一个空的结果串,等会儿每看一个字符就往里添东西。从最左边第 0 个字符开始,一个一个往右看。
- 5扫到第 0 位,是数字 "1"。它不是小数点,处理起来最简单。
- 6不是小数点,就把 "1" 原封不动接到结果串后面。现在结果串是 "1"。这一位也搞定,往后走。
- 7扫到第 1 位,是数字 "0"。它不是小数点,处理起来最简单。
- 8不是小数点,就把 "0" 原封不动接到结果串后面。现在结果串是 "10"。这一位也搞定,往后走。
- 9扫到第 2 位,是数字 "0"。它不是小数点,处理起来最简单。
- 10不是小数点,就把 "0" 原封不动接到结果串后面。现在结果串是 "100"。这一位也搞定,往后走。
- 11扫到第 3 位,是一个小数点 "."。按规矩,小数点不能直接抄,得换个写法。
- 12是小数点,就往结果串后面写上 "[.]" 这三个字符,代替原来的一个点。写完结果串变成 "100[.]"。这一位处理好了,继续看下一个。
- 13扫到第 4 位,是数字 "2"。它不是小数点,处理起来最简单。
- 14不是小数点,就把 "2" 原封不动接到结果串后面。现在结果串是 "100[.]2"。这一位也搞定,往后走。
- 15扫到第 5 位,是一个小数点 "."。按规矩,小数点不能直接抄,得换个写法。
- 16是小数点,就往结果串后面写上 "[.]" 这三个字符,代替原来的一个点。写完结果串变成 "100[.]2[.]"。这一位处理好了,继续看下一个。
- 17扫到第 6 位,是数字 "3"。它不是小数点,处理起来最简单。
- 18不是小数点,就把 "3" 原封不动接到结果串后面。现在结果串是 "100[.]2[.]3"。这一位也搞定,往后走。
- 19扫到第 7 位,是数字 "0"。它不是小数点,处理起来最简单。
- 20不是小数点,就把 "0" 原封不动接到结果串后面。现在结果串是 "100[.]2[.]30"。这一位也搞定,往后走。
- 21扫到第 8 位,是一个小数点 "."。按规矩,小数点不能直接抄,得换个写法。
- 22是小数点,就往结果串后面写上 "[.]" 这三个字符,代替原来的一个点。写完结果串变成 "100[.]2[.]30[.]"。这一位处理好了,继续看下一个。
- 23扫到第 9 位,是数字 "4"。它不是小数点,处理起来最简单。
- 24不是小数点,就把 "4" 原封不动接到结果串后面。现在结果串是 "100[.]2[.]30[.]4"。这一位也搞定,往后走。
- 2510 个字符全扫完了。原串里的 3 个小数点都换成了 "[.]",数字一个没动,拼出来就是 "100[.]2[.]30[.]4"。可以对一下:原来的 "100.2.30.4" 里三个点的位置,现在各是一段 "[.]",答案 "100[.]2[.]30[.]4" 成立。
⚠️ 容易写错的地方
✗ 错：把别的符号(像冒号)也跟着换了
✓ 对：只替换小数点 "." 这一种字符
题目只要求把 "." 换成 "[.]",数字和其它字符必须原样保留
✗ 错：Java 里担心 replace 把 "." 当成正则通配符
✓ 对：String.replace 收的是字面字符,不走正则,点就是点
只有 replaceAll 才按正则解析,那时才需要把 "." 转义成 "\."
✗ 错：从左往右原地替换,导致后面字符下标错乱
✓ 对：从右往左改,或者另开一个新串来拼
"[.]" 比一个点长,从左原地插入会把后面字符顶到更后面,下标全乱
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def defangIPaddr(self, address: str) -> str:
return address.replace('.', '[.]')C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
string defangIPaddr(string address) {
for (int i = address.size(); i >= 0; --i) {
if (address[i] == '.') {
address.replace(i, 1, "[.]");
}
}
return address;
}
};Java
import java.util.*;
class Solution {
public String defangIPaddr(String address) {
return address.replace(".", "[.]");
}
}复杂度
时间
O(n)
n 为地址长度。每个字符只看一遍,判断是不是小数点再决定抄一个还是写三个,整体是线性扫描
空间
O(n)
要生成一个新字符串放结果。每个小数点会变成 3 个字符,所以新串长度最多约 3n,按峰值占用算是线性
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 IP 地址无效化 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么 C++ 那版要从右往左替换?+
因为替换时 "[.]" 比原来的一个 "." 长,会把它后面的所有字符都往后顶,下标跟着右移。如果从左往右就地改,改完前面的点,后面还没扫到的字符位置就全乱了。从右往左改就没这个烦恼:已经改过的都在右边,左边还没扫到的部分下标一点没变。要是用语言自带的 replace 或者另开一个新串来拼,就完全不用操心下标问题。
时间和空间复杂度是多少?+
时间 O(n),n 是地址长度,每个字符只看一遍。空间 O(n),因为要生成一个新字符串,每个小数点会膨胀成三个字符,新串长度最多约是原串的三倍,仍然是线性级别。
实际工程里最简洁的写法是什么?+
直接用语言内置的字符串替换函数。Python 和 Java 都是一行 address.replace(".", "[.]"),可读性最好也最不容易出错。只有在没有现成替换函数、或者要练手动操作时,才会像 C++ 这版那样逐字符扫描自己拼。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 IP 地址无效化 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。