LeetCode 比较版本号：从 split 解法到双指针优化，彻底讲懂这道题
一、题目描述
LeetCode 上有一道经典字符串题：比较版本号。
题目大意是：
给你两个版本号字符串version1和version2，请你比较它们的大小。
版本号由若干个修订号组成，修订号之间用点号.分隔。
例如：
"1.0.3" "1.02.4" "2.1"每一个被.分开的部分，叫做一个修订号。
题目要求：
从左到右依次比较每一个修订号。
修订号比较时，要转换成整数。
前导零需要忽略。
如果某个版本号的修订号数量较少，那么缺失的部分当成
0。如果
version1 > version2，返回1。如果
version1 < version2，返回-1。如果二者相等，返回
0。
二、先看几个例子
示例一
version1 = "1.01" version2 = "1.001"表面上看：
"01" "001"字符串不一样。
但是题目说，修订号要转换成整数，并忽略前导零。
所以：
Number("01") === 1 Number("001") === 1因此：
"1.01" 和 "1.001" 相等返回：
0示例二
version1 = "1.0" version2 = "1.0.0"拆开后：
version1 = ["1", "0"] version2 = ["1", "0", "0"]version1少了最后一个修订号。
题目规定，缺失的修订号当成0。
所以可以理解成：
version1 = ["1", "0", "0"] version2 = ["1", "0", "0"]因此二者相等，返回：
0示例三
version1 = "1.0.1" version2 = "1"拆开后：
version1 = ["1", "0", "1"] version2 = ["1"]逐段比较：
第一段：1 == 1 第二段：0 == 0 第三段：1 > 0所以：
"1.0.1" > "1"返回：
1三、为什么不能直接比较字符串？
很多初学者看到这个题，第一反应可能是直接比较：
if (version1 > version2) return 1; if (version1 < version2) return -1; return 0;这样是不对的。
比如：
version1 = "1.10" version2 = "1.2"从版本号规则来看：
第一段：1 == 1 第二段：10 > 2所以：
"1.10" > "1.2"但是如果按字符串比较，"10"和"2"会按照字符顺序比较。
字符串"10"的第一个字符是"1"，字符串"2"的第一个字符是"2"。
因为：
"1" < "2"所以字符串比较会错误地认为：
"10" < "2"这显然不符合版本号比较规则。
所以这道题不能直接比较整个字符串，必须按照.分割出来的每一段数字进行比较。
四、普通解法：split 分割
最容易想到的解法是：
使用
split(".")把两个版本号拆成数组。找到两个数组中较长的长度。
从左到右逐段比较。
每一段都转成数字。
如果某个数组没有当前段，就当成
0。
代码如下：
var compareVersion = function(version1, version2) { const arr1 = version1.split("."); const arr2 = version2.split("."); const len = Math.max(arr1.length, arr2.length); for (let i = 0; i < len; i++) { const num1 = Number(arr1[i] || 0); const num2 = Number(arr2[i] || 0); if (num1 > num2) { return 1; } if (num1 < num2) { return -1; } } return 0; };这段代码比较直观，适合刚开始理解这道题。
五、split 解法的问题
split解法虽然简单，但是它会创建额外数组。
比如：
"1.02.003.4".split(".")会得到：
["1", "02", "003", "4"]也就是说，它会先把整个字符串全部拆开，然后再比较。
但是实际上，比较版本号的时候，并不一定需要知道后面所有修订号。
比如：
version1 = "2.0.0.0.0" version2 = "1.999.999.999"第一段比较：
2 > 1结果已经确定了。
后面的内容根本不需要再看。
所以，split解法有一个缺点：
空间复杂度是 O(n + m)其中n和m分别是两个版本号字符串的长度。
那么有没有办法不创建数组，一边扫描一边比较呢？
答案就是：双指针。
六、双指针解法核心思想
双指针解法的核心是：
不提前拆分字符串，而是用两个指针分别扫描
version1和version2，每次取出当前修订号进行比较。
定义两个指针：
let i = 0; let j = 0;其中：
i 指向 version1 当前扫描的位置 j 指向 version2 当前扫描的位置每一轮循环中，我们分别从version1和version2中读取一个修订号。
比如：
version1 = "1.01.3" version2 = "1.001.2"第一轮读取：
version1 当前修订号：1 version2 当前修订号：1第二轮读取：
version1 当前修订号：01，转换成整数是 1 version2 当前修订号：001，转换成整数是 1第三轮读取：
version1 当前修订号：3 version2 当前修订号：2发现：
3 > 2所以直接返回：
1七、如何一边扫描一边把字符串转成数字？
假设当前要读取这一段：
"123"我们可以从左到右扫描。
初始：
num = 0读到字符'1'：
num = num * 10 + 1 num = 0 * 10 + 1 num = 1读到字符'2'：
num = num * 10 + 2 num = 1 * 10 + 2 num = 12读到字符'3'：
num = num * 10 + 3 num = 12 * 10 + 3 num = 123所以代码可以这样写：
num = num * 10 + Number(version[i]);这就是手动把字符串数字转换成整数。
八、为什么前导零会自动被忽略？
比如当前修订号是：
"001"初始：
num = 0读到第一个'0'：
num = 0 * 10 + 0 num = 0读到第二个'0'：
num = 0 * 10 + 0 num = 0读到'1'：
num = 0 * 10 + 1 num = 1所以"001"最后得到的数字就是1。
前导零自然就被忽略了。
这也是双指针解法非常巧妙的地方。
九、双指针完整代码
var compareVersion = function(version1, version2) { let i = 0; let j = 0; const n = version1.length; const m = version2.length; while (i < n || j < m) { let num1 = 0; let num2 = 0; while (i < n && version1[i] !== ".") { num1 = num1 * 10 + Number(version1[i]); i++; } while (j < m && version2[j] !== ".") { num2 = num2 * 10 + Number(version2[j]); j++; } if (num1 > num2) { return 1; } if (num1 < num2) { return -1; } i++; j++; } return 0; };十、代码详细讲解
1. 初始化两个指针
let i = 0; let j = 0;i用来遍历version1。
j用来遍历version2。
它们都从字符串的第一个字符开始扫描。
2. 保存字符串长度
const n = version1.length; const m = version2.length;后面循环时需要判断指针有没有越界，所以先保存两个字符串的长度。
3. 外层循环为什么用||
while (i < n || j < m) {这里一定要注意，是||，不是&&。
原因是：只要有一个版本号还没扫描完，就应该继续比较。
比如：
version1 = "1.0.1" version2 = "1"当version2扫描完之后，version1后面还有：
.0.1这些内容仍然需要和version2缺失的修订号0比较。
如果写成：
while (i < n && j < m)那么只要有一个字符串结束，循环就停止了。
这样会错误地认为：
"1.0.1" 和 "1" 相等但实际上：
"1.0.1" > "1"所以外层循环必须写成：
while (i < n || j < m)4. 每一轮重新计算当前修订号
let num1 = 0; let num2 = 0;每次进入外层循环，都表示要比较一个新的修订号。
所以num1和num2都要重新初始化为0。
5. 读取 version1 当前修订号
while (i < n && version1[i] !== ".") { num1 = num1 * 10 + Number(version1[i]); i++; }这段代码的作用是：从当前位置i开始，一直读取到下一个.为止。
例如：
version1 = "1.02.3"第一轮时，i指向：
1.02.3 ^ i读取到数字1后，i继续往后走。
当i指向.时：
1.02.3 ^ i说明当前修订号已经读完了。
于是内部循环停止。
此时num1就是当前修订号的整数值。
6. 读取 version2 当前修订号
while (j < m && version2[j] !== ".") { num2 = num2 * 10 + Number(version2[j]); j++; }这段逻辑和version1完全一样。
它负责读取version2的当前修订号。
7. 比较当前两个修订号
if (num1 > num2) { return 1; } if (num1 < num2) { return -1; }版本号比较是从左到右逐级比较。
只要当前修订号已经分出大小，整个版本号的大小就确定了。
例如：
version1 = "2.0.0" version2 = "1.999.999"第一段：
2 > 1所以直接返回1。
后面的：
0.0 999.999已经不需要再比较了。
8. 为什么最后要i++和j++
i++; j++;内部循环停止时，指针通常会停在.的位置。
比如：
version1 = "1.02.3"读取完第一段1后，i停在：
1.02.3 ^ i下一轮我们不希望从.开始读，而是希望跳过这个点，从下一个数字开始读。
所以需要：
i++;这样i就移动到：
1.02.3 ^ ij++的作用也是一样。
9. 字符串结束后继续i++会不会出错？
不会。
因为读取修订号的时候有判断：
while (i < n && version1[i] !== ".")如果i已经超过了字符串范围，i < n不成立，就不会进入循环。
此时：
num1 = 0刚好表示缺失的修订号为0。
比如：
version1 = "1" version2 = "1.0.0"第一轮比较：
num1 = 1 num2 = 1相等。
之后version1已经结束了。
第二轮：
num1 = 0 num2 = 0第三轮：
num1 = 0 num2 = 0最后所有修订号都相等，所以返回：
0这正好符合题意。
十一、完整执行过程示例
以这个例子为例：
version1 = "1.0.1" version2 = "1"初始：
i = 0 j = 0第一轮
读取version1当前修订号：
num1 = 1读取version2当前修订号：
num2 = 1比较：
num1 == num2继续下一轮。
第二轮
version1读取到第二段：
num1 = 0version2已经结束，缺失部分当成0：
num2 = 0比较：
num1 == num2继续下一轮。
第三轮
version1读取到第三段：
num1 = 1version2仍然已经结束，缺失部分当成0：
num2 = 0比较：
num1 > num2所以返回：
1说明：
"1.0.1" > "1"十二、复杂度分析
设version1的长度为n，version2的长度为m。
双指针扫描过程中，每个字符最多被访问一次。
所以时间复杂度是：
O(n + m)整个过程中，只使用了：
i j num1 num2 n m这些变量，没有创建额外数组。
所以空间复杂度是：
O(1)十三、split 解法和双指针解法对比
| 解法 | 思路 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|---|
| split 解法 | 先按.分割成数组，再逐段比较 | O(n + m) | O(n + m) | 简单直观 | 需要额外数组 |
| 双指针解法 | 一边扫描一边读取当前修订号 | O(n + m) | O(1) | 空间更优 | 代码理解稍难 |
实际刷题时，如果只是想快速通过，split解法完全可以。
但如果想写出更优解，或者面试时体现对空间复杂度的优化，双指针解法更合适。
十四、这道题的关键点总结
这道题看起来是字符串比较，实际上考察的是：
能不能正确理解版本号的比较规则。
能不能避免直接字符串比较的错误。
能不能处理前导零。
能不能处理版本号长度不一致的情况。
能不能用双指针优化空间复杂度。
最终双指针解法可以概括为一句话：
用两个指针分别扫描两个版本号字符串，每次读取一个修订号，转成整数后比较；如果当前修订号不同，立即返回结果；如果全部相同，则返回 0。
十五、最终推荐代码
var compareVersion = function(version1, version2) { let i = 0; let j = 0; const n = version1.length; const m = version2.length; while (i < n || j < m) { let num1 = 0; let num2 = 0; while (i < n && version1[i] !== ".") { num1 = num1 * 10 + Number(version1[i]); i++; } while (j < m && version2[j] !== ".") { num2 = num2 * 10 + Number(version2[j]); j++; } if (num1 > num2) { return 1; } if (num1 < num2) { return -1; } i++; j++; } return 0; };这份代码的优势是：不需要split创建数组，直接在原字符串上扫描，空间复杂度为O(1)，是这道题更优雅的写法。