0165. Compare Version Numbers

题目信息

题号:
  1. 比较版本号

难度:

Medium

主题:

字符串、双指针、分段比较

原题:

LeetCode 0165

重点:

按数值语义比较修订段,用有效数字区间消除前导零、尾部零和整数转换问题

题目重述

给定两个版本字符串 version1 和 version2。每个版本由若干只含数字的修订段组成, 相邻修订段以点号分隔。按从左到右的顺序比较对应修订段的整数值,前导零不影响数值; 若一侧先结束,其后缺失的修订段都视为 0。

若 version1 较小返回 -1,较大返回 1,两者等价返回 0。

自建示例

输入:version1 = "3.10", version2 = "3.9.8"
输出:1

首段同为 3,第二段 10 大于 9;后面的 8 不再影响结果。
输入:version1 = "4.02.0.0", version2 = "4.2"
输出:0

02 与 2 数值相同;第一个版本多出的两个修订段都等于 0。
输入:version1 = "1.0000000000007", version2 = "1.7"
输出:0

删除前导零后,两侧第二段的有效数字都是 7,无需把长文本转换为整数。

C++ 实现

#include <string>

class Solution {
private:
    struct Revision {
        int begin;
        int length;
    };

    Revision readRevision(const std::string& version, int& index) {
        int size = static_cast<int>(version.size());

        while (index < size && version[index] == '0') {
            ++index;
        }
        int begin = index;

        while (index < size && version[index] != '.') {
            ++index;
        }
        int length = index - begin;

        if (index < size) {
            ++index;
        }
        return {begin, length};
    }

    int compareRevision(
        const std::string& first,
        Revision left,
        const std::string& second,
        Revision right) {
        if (left.length != right.length) {
            return left.length < right.length ? -1 : 1;
        }

        for (int offset = 0; offset < left.length; ++offset) {
            char left_digit = first[left.begin + offset];
            char right_digit = second[right.begin + offset];
            if (left_digit != right_digit) {
                return left_digit < right_digit ? -1 : 1;
            }
        }
        return 0;
    }

public:
    int compareVersion(std::string version1, std::string version2) {
        int first_index = 0;
        int second_index = 0;

        while (first_index < static_cast<int>(version1.size()) ||
               second_index < static_cast<int>(version2.size())) {
            Revision left = readRevision(version1, first_index);
            Revision right = readRevision(version2, second_index);
            int order = compareRevision(
                version1, left, version2, right);
            if (order != 0) {
                return order;
            }
        }
        return 0;
    }
};

题解

比较对象不是整个字符串

若直接按字典序比较,"3.10" 会被误判为小于 "3.9",因为字符 '1' 小于 '9';若比较字符串长度,点号数量和前导零又会制造无关差异。题目定义的比较对象 实际上是从左到右排列的整数序列:

"4.02.0.0" -> [4, 2, 0, 0]
"4.2"      -> [4, 2]

两个序列按第一处不同的修订值决定顺序;短序列后面无限补零。因此原始方案可以先按点号 切出全部字符串、转成整数数组,再逐项比较。它是正确的,但创建了两组只使用一次的中间 结果,也让整数转换承担了本可避免的位数和溢出边界。

数值比较可以保留在字符串上

一个非负十进制数删除前导零后,只需两步就能比较大小:

  1. 有效数字位数不同,位数更多的数更大;

  2. 位数相同,从最高位开始逐字符比较,第一处不同的数字决定大小。

全零修订段删除前导零后长度为 0,正好成为统一的“数值 0”表示。这样无需调用 stoi 或 stoll,即使某个修订段文本很长,比较过程也不会发生整数溢出。

Revision 只保存有效数字在原字符串中的 begin 和 length,没有复制子串。 readRevision 先跳过前导零,再找到点号;最后越过点号,使指针直接指向下一段。

同步消费与尾部补零

first_index、second_index 分别表示两个字符串尚未读取的位置。只要任一字符串 仍有内容,循环就同步读取一对修订段并比较:

  • 比较结果非零时立即返回,因为字典式数值序列的第一处差异已经决定全局顺序;

  • 比较结果为零时继续消费下一对修订段;

  • 一侧已经到达末尾时,readRevision 不读取字符并返回长度为 0 的修订段,等价于 为短版本补一个零。

循环不需要真的无限补零。较长一侧的实际尾段全部比较完后,如果它们都为零,两个指针 同时到达末尾并返回 0;只要某个尾段非零,就会当场决定大小。

具体走读

比较 "4.02.0.0" 与 "4.2":

  1. 两侧首段有效区间都是 "4",位数和字符均相同;

  2. 左侧 "02" 跳过一个前导零后只保留 "2",与右侧 "2" 相同;

  3. 右侧已经结束。左侧下一个 "0" 的有效长度为 0,结束侧也返回长度 0;

  4. 最后一段重复同样比较,随后两侧指针都到达末尾,返回 0。

比较 "3.10" 与 "3.9.8" 时,首段相同;第二段有效长度分别为 2 和 1, 无需逐字符读取 10 的大小,更无需检查第三段 8,立即返回 1。

代码状态与边界

读取顺序必须是“跳前导零—记录起点—找段尾—越过点号”。如果先记录起点,长度会把 前导零算进去;如果找到点号后不前进,下一轮会反复读取空段。有效输入不会以空段开始或 结束,但已经结束的一侧允许 begin == size、length == 0,比较函数不会访问该 位置,因此安全地表示补零状态。

复杂度

设两个字符串长度分别为 n、m。每个字符最多在跳过零、寻找段尾或比较有效数字 时被常数次访问,时间复杂度为 O(n + m);只维护两个指针和两个修订段视图,额外空间 复杂度为 O(1)。