165. 比较版本号

题目链接：https://leetcode.cn/problems/compare-version-numbers/

代码

function compareVersion(version1: string, version2: string): number {
    let arr1 = version1.split('.');
    let arr2 = version2.split('.');
    const len = Math.max(arr1.length, arr2.length);
    for (let i = 0; i < len; i++) {
        let num1 = arr1[i] ? parseInt(arr1[i]) : 0;
        let num2 = arr2[i] ? parseInt(arr2[i]) : 0;
        if (num1 > num2) return 1;
        else if (num1 < num2) return -1;
    }
    return 0;
};

function compareVersionNoSplit(version1: string, version2: string): number {
    let i = 0, j = 0;
    while(i < version1.length || j < version2.length){
        let num1 = 0, num2 = 0;
        while(i < version1.length && version1[i] !== '.'){
            num1 = num1 * 10 + parseInt(version1[i]);
            i++;
        }
        while(j < version2.length && version2[j] !== '.'){
            num2 = num2 * 10 + parseInt(version2[j]);
            j++
        }
        i++;
        j++;
        if (num1 > num2) return 1;
        else if (num1 < num2) return -1;
    }
    return 0;
};

思路

这份代码提供了两种写法。

方法一：split 分段比较

1. 用 . 把两个版本号拆成数组
2. 取两者长度的最大值，逐段比较
3. 如果某一方当前段不存在，就按 0 处理
4. 当前段数值较大的一方版本更大
5. 所有段都相等时，返回 0

例如：

• 1.01 和 1.001，每一段转成数字后都相等，结果为 0
• 1.0 和 1.0.1，第三段比较为 0 和 1，结果为 -1

方法二：双指针原地解析

1. 用两个指针分别遍历 version1 和 version2
2. 每次读取一段连续数字，遇到 . 停止
3. 将当前段转成整数后比较大小
4. 比较完后继续处理下一段，直到两个字符串都遍历结束

这种写法不依赖 split，本质上也是按段比较。

关键点

• 版本号比较的是每一段的整数值，而不是字符串字典序

• 前导零不会影响比较结果，因为最终都会转成数字

• 较短版本号缺失的段要按 0 处理

• 时间复杂度 $O(n+m)$，其中 $n$ 和 $m$ 分别是两个字符串的长度

• 空间复杂度：

  • split 写法为 $O(n+m)$
  • 双指针写法为 $O(1)$