☕ DSA Java Articles

Topics › Strings › Medium String Problems

Compare version numbers

Medium TUF ID 198 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A version number is a list of revisions separated by dots, such as "1.0.12". Each revision is a run of digits and may have leading zeros. To compare two version numbers, compare their revisions from left to right as integers (so "001" equals "1"). If one version has fewer revisions, the missing ones count as 0.

Return -1 if version1 < version2, 1 if version1 > version2, and 0 if they are equal.

Constraints (LeetCode 165): 1 ≤ length ≤ 500, only digits and dots, every version is well formed (no empty revisions, no leading or trailing dot), and every revision fits in a 32-bit integer.

Example 1

version1 = "1.2", version2 = "1.10"
answer = -1      // revision 2: 2 < 10 as integers, even though "2" > "10" as text

Example 2

version1 = "1.01", version2 = "1.001"
answer = 0       // both second revisions are the integer 1

Example 3

version1 = "1.0", version2 = "1.0.0.0"
answer = 0       // the missing third and fourth revisions of version1 count as 0

The two traps are visible right in the examples: comparing the whole strings, or individual revisions, as text gets example 1 wrong, and treating “has more revisions” as “is bigger” gets example 3 wrong.

Approach 1: Split and parse

Intuition. Do literally what the statement says. Split each version on dots into an array of revision strings, turn each one into an integer, and walk both arrays in parallel. Where one array has run out, use 0. The first position where the integers differ decides the answer; if none differs, the versions are equal.

Integer.parseInt handles leading zeros for us (parseInt("007") is 7), so all of the integer comparison logic is delegated to the library.

Algorithm.

  1. a = version1.split("\\."), b = version2.split("\\.").
  2. For i from 0 to max(a.length, b.length) - 1: let x be parseInt(a[i]) or 0 if i is past the end of a; same for y.
  3. If x != y, return -1 or 1.
  4. Return 0.
static int splitAndParse(String version1, String version2) {
    String[] a = version1.split("\\."), b = version2.split("\\.");
    int len = Math.max(a.length, b.length);
    for (int i = 0; i < len; i++) {
        int x = i < a.length ? Integer.parseInt(a[i]) : 0;   // parseInt drops leading zeros: "001" -> 1
        int y = i < b.length ? Integer.parseInt(b[i]) : 0;
        if (x != y) return x < y ? -1 : 1;
    }
    return 0;
}

Complexity. Time O(n + m) for splitting and parsing, where n and m are the string lengths. Space O(n + m) for the two arrays of substrings.

Note the double backslash. split takes a regular expression, and in a regex a bare . matches any character, so split(".") would split everywhere and return an empty array. "\\." is the Java string for the regex \., a literal dot.

Approach 2: Optimal, two pointers without splitting

Intuition. The arrays in Approach 1 are only an intermediate step: we read each revision once, in order, and never go back. So we can parse revisions directly out of the strings with one pointer per string. For the current revision, pointer i reads digits of version1 until it hits a dot or the end, accumulating x = x * 10 + digit; pointer j does the same for version2. Compare x and y, then step both pointers over the dot and repeat.

Missing revisions need no special code. Once a pointer is past the end of its string, its digit loop does not run, so that string contributes 0 for every remaining round, exactly as the rules require. The loop continues while either string has characters left.

Leading zeros are also free: x * 10 + 0 with x = 0 stays 0, so "001" parses to 1.

Algorithm.

  1. Set i = j = 0.
  2. While i < n or j < m:
    • Read digits of version1 from i up to the next dot into x (or leave x = 0 if i ≥ n); likewise y from version2.
    • If x != y, return -1 or 1.
    • Advance i and j past the dot.
  3. Return 0.
static int optimal(String version1, String version2) {
    int i = 0, j = 0, n = version1.length(), m = version2.length();
    while (i < n || j < m) {
        int x = 0, y = 0;                                    // an exhausted string contributes 0
        while (i < n && version1.charAt(i) != '.') x = x * 10 + (version1.charAt(i++) - '0');
        while (j < m && version2.charAt(j) != '.') y = y * 10 + (version2.charAt(j++) - '0');
        if (x != y) return x < y ? -1 : 1;
        i++;                                                 // step over the '.' (or past the end)
        j++;
    }
    return 0;
}

Dry run on two pairs:

pair round x y result
"1.2" vs "1.10" 1 1 1 equal, continue
  2 2 10 x < y, return -1
"1.0" vs "1.0.0.0" 1 1 1 equal
  2 0 0 equal
  3 0 (exhausted) 0 equal
  4 0 (exhausted) 0 equal, loop ends, return 0

Complexity. Time O(n + m): each character is read once. Space O(1): a few integers and no substrings.

Approach 3: Revisions of any length, without converting

Intuition. Approaches 1 and 2 both rely on the guarantee that a revision fits in an int. Real version strings sometimes contain long numbers (build timestamps, for instance), and then parseInt throws and the on-the-fly sum silently overflows. We can compare two non-negative integers written in decimal without ever converting them:

  1. Leading zeros carry no value, so skip them.
  2. After that, the number with more digits is larger. A number with no remaining digits is 0.
  3. If both have the same number of digits, the first position where the digits differ decides, exactly like comparing words in a dictionary.

Apply this to each pair of revisions in turn, with the same two-pointer walk as before. Each revision is described by the start index of its first significant digit and the count of significant digits.

Algorithm.

  1. While either string has characters left:
    • In each string, skip leading '0's, remember the start, and move to the next dot. The difference is the number of significant digits.
    • If the digit counts differ, the one with more digits is larger.
    • Otherwise compare digit by digit; the first difference decides.
    • Step both pointers over the dot.
  2. Return 0.
static int digitStrings(String version1, String version2) {
    int i = 0, j = 0, n = version1.length(), m = version2.length();
    while (i < n || j < m) {
        while (i < n && version1.charAt(i) == '0') i++;      // leading zeros carry no value
        while (j < m && version2.charAt(j) == '0') j++;
        int si = i, sj = j;
        while (i < n && version1.charAt(i) != '.') i++;
        while (j < m && version2.charAt(j) != '.') j++;
        int lenX = i - si, lenY = j - sj;                    // number of significant digits (0 means the value 0)
        if (lenX != lenY) return lenX < lenY ? -1 : 1;
        for (int k = 0; k < lenX; k++) {                     // same length: the first differing digit decides
            char cx = version1.charAt(si + k), cy = version2.charAt(sj + k);
            if (cx != cy) return cx < cy ? -1 : 1;
        }
        i++;
        j++;
    }
    return 0;
}

Complexity. Time O(n + m): every character is skipped, measured or compared a constant number of times. Space O(1).

This version passes all the same tests as the other two, and also handles inputs such as "1.99999999999999999999" vs "1.100000000000000000000" (20 digits vs 21, so -1) that would break the integer-based methods.

Edge cases and pitfalls