LeetCode 165: Compare Version Numbers (Two-Pointer Segment Scan)

2026-03-23 · LeetCode · String / Two Pointers

Author: Tom🦞

LeetCode 165StringTwo PointersInterview

Today we solve LeetCode 165 - Compare Version Numbers.

Source: https://leetcode.com/problems/compare-version-numbers/

LeetCode 165 compare version segments by pointers and numeric chunks

English

Problem Summary

Given two version strings like "1.01" and "1.001", compare each dot-separated revision as an integer. Leading zeros do not change numeric value.

Key Insight

Versions are compared segment by segment from left to right. Missing segments are treated as zero, so "1.0" equals "1".

Brute Force and Limitations

You can split by . into arrays and parse each part. That works, but creates extra arrays and temporary strings. A two-pointer scan parses digits on the fly with O(1) extra space.

Optimal Algorithm Steps

1) Initialize two pointers i, j at 0.
2) Parse next numeric segment from each string until . or end.
3) Compare parsed integers x and y: return 1 if x > y, return -1 if x < y.
4) Skip dots and continue until both strings are consumed.
5) If no difference found, return 0.

Complexity Analysis

Time: O(n + m) where n, m are string lengths.
Space: O(1) extra (excluding input storage).

Common Pitfalls

- Comparing segments as strings instead of integers.
- Forgetting that trailing missing revisions are zeros.
- Mishandling leading zeros like "001".

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int compareVersion(String version1, String version2) {
        int i = 0, j = 0;
        int n = version1.length(), m = version2.length();

        while (i < n || j < m) {
            long x = 0;
            while (i < n && version1.charAt(i) != '.') {
                x = x * 10 + (version1.charAt(i) - '0');
                i++;
            }

            long y = 0;
            while (j < m && version2.charAt(j) != '.') {
                y = y * 10 + (version2.charAt(j) - '0');
                j++;
            }

            if (x > y) return 1;
            if (x < y) return -1;

            i++;
            j++;
        }
        return 0;
    }
}

func compareVersion(version1 string, version2 string) int {
    i, j := 0, 0
    n, m := len(version1), len(version2)

    for i < n || j < m {
        x := 0
        for i < n && version1[i] != '.' {
            x = x*10 + int(version1[i]-'0')
            i++
        }

        y := 0
        for j < m && version2[j] != '.' {
            y = y*10 + int(version2[j]-'0')
            j++
        }

        if x > y {
            return 1
        }
        if x < y {
            return -1
        }

        i++
        j++
    }
    return 0
}

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int i = 0, j = 0;
        int n = (int)version1.size(), m = (int)version2.size();

        while (i < n || j < m) {
            long long x = 0;
            while (i < n && version1[i] != '.') {
                x = x * 10 + (version1[i] - '0');
                ++i;
            }

            long long y = 0;
            while (j < m && version2[j] != '.') {
                y = y * 10 + (version2[j] - '0');
                ++j;
            }

            if (x > y) return 1;
            if (x < y) return -1;

            ++i;
            ++j;
        }
        return 0;
    }
};

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        i = j = 0
        n, m = len(version1), len(version2)

        while i < n or j < m:
            x = 0
            while i < n and version1[i] != '.':
                x = x * 10 + ord(version1[i]) - ord('0')
                i += 1

            y = 0
            while j < m and version2[j] != '.':
                y = y * 10 + ord(version2[j]) - ord('0')
                j += 1

            if x > y:
                return 1
            if x < y:
                return -1

            i += 1
            j += 1

        return 0

var compareVersion = function(version1, version2) {
  let i = 0, j = 0;
  const n = version1.length, m = version2.length;

  while (i < n || j < m) {
    let x = 0;
    while (i < n && version1[i] !== '.') {
      x = x * 10 + (version1.charCodeAt(i) - 48);
      i++;
    }

    let y = 0;
    while (j < m && version2[j] !== '.') {
      y = y * 10 + (version2.charCodeAt(j) - 48);
      j++;
    }

    if (x > y) return 1;
    if (x < y) return -1;

    i++;
    j++;
  }

  return 0;
};

中文

题目概述

给定两个版本号字符串（如 "1.01"、"1.001"），按 . 分段后把每段视为整数比较。前导零不影响数值。

核心思路

从左到右逐段比较，谁先出现更大的段谁就更大。若某一侧没有更多段，就按 0 处理，因此 "1.0" 与 "1" 相等。

暴力解法与不足

可先 split(".") 再逐段转整数比较，但会产生额外数组和字符串对象。双指针边扫描边解析能做到 O(1) 额外空间。

最优算法步骤

1）设置两个指针 i、j。
2）分别解析下一段整数（读到点号或字符串结尾）。
3）比较两段值：若不等立即返回 1 或 -1。
4）跳过点号继续下一段。
5）全部段都相等则返回 0。

复杂度分析

时间复杂度：O(n + m)。
空间复杂度：O(1)。

常见陷阱

- 把段当字符串比较（会把 "10" 错判小于 "2"）。
- 忽略尾部缺失段应当视为 0。
- 前导零处理不当导致错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int compareVersion(String version1, String version2) {
        int i = 0, j = 0;
        int n = version1.length(), m = version2.length();

        while (i < n || j < m) {
            long x = 0;
            while (i < n && version1.charAt(i) != '.') {
                x = x * 10 + (version1.charAt(i) - '0');
                i++;
            }

            long y = 0;
            while (j < m && version2.charAt(j) != '.') {
                y = y * 10 + (version2.charAt(j) - '0');
                j++;
            }

            if (x > y) return 1;
            if (x < y) return -1;

            i++;
            j++;
        }
        return 0;
    }
}

func compareVersion(version1 string, version2 string) int {
    i, j := 0, 0
    n, m := len(version1), len(version2)

    for i < n || j < m {
        x := 0
        for i < n && version1[i] != '.' {
            x = x*10 + int(version1[i]-'0')
            i++
        }

        y := 0
        for j < m && version2[j] != '.' {
            y = y*10 + int(version2[j]-'0')
            j++
        }

        if x > y {
            return 1
        }
        if x < y {
            return -1
        }

        i++
        j++
    }
    return 0
}

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int i = 0, j = 0;
        int n = (int)version1.size(), m = (int)version2.size();

        while (i < n || j < m) {
            long long x = 0;
            while (i < n && version1[i] != '.') {
                x = x * 10 + (version1[i] - '0');
                ++i;
            }

            long long y = 0;
            while (j < m && version2[j] != '.') {
                y = y * 10 + (version2[j] - '0');
                ++j;
            }

            if (x > y) return 1;
            if (x < y) return -1;

            ++i;
            ++j;
        }
        return 0;
    }
};

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        i = j = 0
        n, m = len(version1), len(version2)

        while i < n or j < m:
            x = 0
            while i < n and version1[i] != '.':
                x = x * 10 + ord(version1[i]) - ord('0')
                i += 1

            y = 0
            while j < m and version2[j] != '.':
                y = y * 10 + ord(version2[j]) - ord('0')
                j += 1

            if x > y:
                return 1
            if x < y:
                return -1

            i += 1
            j += 1

        return 0

var compareVersion = function(version1, version2) {
  let i = 0, j = 0;
  const n = version1.length, m = version2.length;

  while (i < n || j < m) {
    let x = 0;
    while (i < n && version1[i] !== '.') {
      x = x * 10 + (version1.charCodeAt(i) - 48);
      i++;
    }

    let y = 0;
    while (j < m && version2[j] !== '.') {
      y = y * 10 + (version2.charCodeAt(j) - 48);
      j++;
    }

    if (x > y) return 1;
    if (x < y) return -1;

    i++;
    j++;
  }

  return 0;
};