165. Compare Version Numbers
Model: qwen3.5:9b
Topics: String
FAANG asked: 1
Acceptance rate: 30.6%
Problem Breakdown
We are given two version number strings separated by dots (.), such as "2.5" and 3. We need to determine their relative order based on integer values of each revision segment from left to right.
Key Rules:
- Revision Comparison: Compare segments sequentially (index 0, then index 1, etc.).
- Leading Zeros: Segments like
"01"and"1"are treated as equal integers (1). - Missing Revisions: If one string has fewer revisions than the other, treat missing subsequent revisions in the shorter version as
0. For example,"1.0"vs"1", revision index 2 for"1"is implicitly0.
Inputs: Two strings containing digits and dots (lengths up to 500).
Outputs: -1 if version1 < version2, 1 if greater, 0 otherwise.
Intuition
A naive approach might be string comparison or converting the whole string to a number, but that fails because "9" is not less than "8.5". We must compare segment by segment.
The core insight is that this problem reduces to comparing two lists of integers side-by-side until we find a difference. Since Python handles arbitrary precision integers automatically (and constraints say revisions fit in 32-bit int), converting each substring directly to an integer strips leading zeros for us naturally (int("01") becomes 1).
The tricky part is handling the case where one string runs out of segments before the other. We don’t need to physically pad the shorter list with "0" strings; we can simply check if a pointer index exists in our split lists and default to 0 if it doesn’t.
Approach
- Split: Convert both input strings into lists using
.split('.'). This gives us access to individual revisions easily. - Iterate: Use two pointers (or indices) for the current revision index of each list, say
iandj, or simply iterate a single counter while checking bounds against both lists’ lengths. A loop running until both lists are exhausted is safest logic-wise to ensure we check all necessary revisions including implicit zeros at the end if one string was longer (though actually, once indices exceed length, values become 0). - Compare: In each iteration:
- Get current revision from
version1list or default to'0'. - Get current revision from
version2list or default to'0'. - Convert both strings to integers (
int()handles leading zeros). - If values differ, return the result immediately.
- Get current revision from
- Finish: If loop completes without returning (all compared revisions equal), return
0.
Complexity Analysis
- Time Complexity: where and are lengths of
version1andversion2. Splitting the string takes linear time, iterating through segments is proportional to the number of dots (bounded by length). Converting substrings to integers is bounded by substring length. - Space Complexity: due to storing the split lists in memory. Given constraints (), this overhead is negligible, but strictly speaking, we could parse character-by-character for extra space if needed (though Python’s string immutability makes splitting cleaner).
Solution
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
# Split strings into lists of revision substrings.
# This handles the dot separation naturally.
v1_parts = version1.split('.')
v2_parts = version2.split('.')
i, j = 0, 0
# Iterate while there are revisions left in either list to check.
# We continue until both lists have been fully traversed conceptually.
# However, since missing parts act as '0', we can stop once
# the remaining implicit zeros match (which they always do).
# So loop condition is simply: while i < len(v1) or j < len(v2)
while i < len(v1_parts) or j < len(v2_parts):
rev1 = int(v1_parts[i]) if i < len(v1_parts) else 0
rev2 = int(v2_parts[j]) if j < len(v2_parts) else 0
if rev1 > rev2:
return 1
elif rev1 < rev2:
return -1
# Move to next revision for both lists.
# If one list is exhausted, the pointer stays at its limit (handled by condition).
i += 1
j += 1
return 0
# Alternative concise implementation using zip and padding logic implicitly via loop bounds:
Edge Cases Handled
- Leading Zeros:
int("007")correctly evaluates to7, matching"7". The code handles this automatically. - Unequal Lengths: If one version has more revisions (e.g., “1.2” vs “1”), the loop continues until both indices exceed their respective list lengths, treating missing parts as 0 implicitly via the conditional check
if i < len(...) else 0. - Single Revision: Works correctly if split results in a single-element list or empty (though constraints say at least one char).
- Implicit Zeros: Once all explicit revisions match and both lists are exhausted, the loop terminates returning
0, which is correct because remaining implicit zeros for longer strings equal 0.