Compare Version Numbers

LeetCode 165 | Difficulty: Medium

Medium

Problem Description

Given two version strings, version1 and version2, compare them. A version string consists of revisions separated by dots '.'. The value of the revision is its integer conversion ignoring leading zeros.

To compare version strings, compare their revision values in left-to-right order. If one of the version strings has fewer revisions, treat the missing revision values as 0.

Return the following:

- If `version1  version2`, return 1.

- Otherwise, return 0.

Example 1:

Input: version1 = "1.2", version2 = "1.10"

Output: -1

Explanation:

version1's second revision is "2" and version2's second revision is "10": 2 version1 = "1.01", version2 = "1.001"

Output: 0

Explanation:

Ignoring leading zeroes, both "01" and "001" represent the same integer "1".

Example 3:

Input: version1 = "1.0", version2 = "1.0.0.0"

Output: 0

Explanation:

version1 has less revisions, which means every missing revision are treated as "0".

Constraints:

- `1 <= version1.length, version2.length <= 500`

- `version1` and `version2` only contain digits and `'.'`.

- `version1` and `version2` **are valid version numbers**.

- All the given revisions in `version1` and `version2` can be stored in a **32-bit integer**.

Topics: Two Pointers, String

---

Solutions

Solution 1: C# (Best: 105 ms)

Metric	Value
Runtime	105 ms
Memory	35.5 MB
Date	2022-02-25

Solution

public class Solution {
    public int CompareVersion(string version1, string version2) {
        int[] v1 = version1.Split('.').Select(x => Convert.ToInt32(x)).ToArray();
    int[] v2 = version2.Split('.').Select(x => Convert.ToInt32(x)).ToArray();
    int len1 = v1.Length, len2 = v2.Length;
    int len = Math.Max(v1.Length, v2.Length);
    
    for (int i = 0; i < len; i++)
    {
        int val1 = i >= len1 ? 0 : v1[i];
        int val2 = i >= len2 ? 0 : v2[i];
        if(val1 == val2) continue;
        else return val1.CompareTo(val2);
    }
    
    return 0;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: You can use two pointers for each version string to traverse them together while comparing the corresponding segments.

Hint 2: Utilize the substring method to extract each version segment delimited by '.'. Ensure you're extracting the segments correctly by adjusting the start and end indices accordingly.