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:
version1 < version2, return -1.version1 > version2, return 1.
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 < 10, so version1 < version2.
Example 2:
Input: 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 <= 500version1 and version2 only contain digits and '.'.version1 and version2 are valid version numbers.version1 and version2 can be stored in a 32-bit integer.Problem Overview: You are given two version strings such as "1.01" and "1.001". Each version is composed of revisions separated by dots. The task is to compare them numerically revision by revision and return whether one version is greater, smaller, or equal.
Approach 1: Split and Compare Each Component (O(n) time, O(n) space)
The most direct solution splits both version strings using the dot delimiter and compares the resulting revision numbers. Each component is parsed as an integer to ignore leading zeros. Iterate through both arrays simultaneously and compare corresponding revisions. If one version has fewer parts, treat missing revisions as 0. This approach is straightforward and easy to implement using built-in string utilities, making it a practical choice during interviews when clarity matters more than micro-optimizations.
Most languages provide efficient split operations, so implementation becomes a simple loop comparing integers. However, splitting creates extra arrays, which introduces O(n) space complexity. For extremely long version strings or memory-constrained environments, avoiding additional allocations can be beneficial. The approach relies purely on string manipulation and sequential iteration.
Approach 2: Two-pointer Comparison Traversal (O(n) time, O(1) space)
This method avoids splitting entirely by scanning both version strings using two pointers. Each pointer traverses its string and constructs the current revision number digit by digit until reaching a dot or the end. After parsing the current revision for both strings, compare the two integers. If they differ, return the result immediately. Otherwise, move past the dot and continue processing the next revision.
The key insight is that each revision can be built incrementally while traversing the string, eliminating the need for intermediate arrays. Missing revisions naturally evaluate to 0 once a pointer reaches the end of its string. This keeps space usage constant while still processing every character once, resulting in O(n) time complexity. This pattern frequently appears in problems involving segmented string comparisons.
Recommended for interviews: Start with the split-based approach because it clearly communicates the logic of comparing revision numbers. After that, mention the two-pointer traversal as an optimization that removes extra memory usage. Interviewers often expect candidates to recognize the two pointers technique for parsing structured string input efficiently.
This approach involves splitting the version strings into individual components using the dot delimiter. We then convert these components into integers and compare them one by one. If one version string is shorter, we treat the missing components as 0, allowing a fair comparison.
The C solution uses strtok to split the version strings by dot character. Each component is converted to an integer using atoi. We then compare corresponding components, returning -1 or 1 if one is smaller or greater, respectively. The loop continues until all components are compared.
Time Complexity: O(n + m), where n and m are lengths of version1 and version2 respectively.
Space Complexity: O(n + m) for holding the split components.
This approach utilizes two pointers to traverse each version string's components simultaneously. By identifying and isolating numerical values between dots without splitting the string, we optimize for memory usage. Each number is evaluated and compared until a determination is made or the end is reached.
The C solution employs a method where pointers traverse each version string, constructing numerical values between dots manually. This avoids unnecessary string operations and directly compares values to determine the result.
Time Complexity: O(n + m), where n and m are the lengths of version1 and version2.
Space Complexity: O(1), as no significant additional space is used.
Traverse both strings simultaneously using two pointers i and j, which point to the current positions in each string, starting with i = j = 0.
Each time, extract the corresponding revision numbers from both strings, denoted as a and b. Compare a and b: if a \lt b, return -1; if a \gt b, return 1; if a = b, continue to compare the next pair of revision numbers.
The time complexity is O(max(m, n)), and the space complexity is O(1), where m and n are the lengths of the two strings.
| Approach | Complexity |
|---|---|
| Split and Compare Each Component | Time Complexity: O(n + m), where n and m are lengths of version1 and version2 respectively. |
| Two-pointer Comparison Traversal | Time Complexity: O(n + m), where n and m are the lengths of version1 and version2. |
| Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Split and Compare Each Component | O(n) | O(n) | Best for readability and quick implementation using built-in string split utilities. |
| Two-pointer Comparison Traversal | O(n) | O(1) | Preferred when minimizing memory usage or demonstrating deeper string parsing skills. |
Leetcode 165: Compare Version Numbers with stringstream | StringTokenizer | codestorywithMIK • codestorywithMIK • 13,764 views views
Watch 9 more video solutions →Practice Compare Version Numbers with our built-in code editor and test cases.
Practice on FleetCode