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.The key idea in Compare Version Numbers is to compare each numeric revision separated by dots in the version strings. Instead of comparing the strings directly, treat every segment between dots as an integer. This avoids issues caused by leading zeros such as "01" and "1", which represent the same revision.
A common strategy is to either split the versions by the dot character or traverse both strings using a two-pointer approach. At each step, extract the next numeric segment, convert it to an integer, and compare it with the corresponding segment from the other version. If one version runs out of segments, treat the missing revision as 0. Continue until a difference is found or all segments are compared.
This method ensures accurate comparison while avoiding unnecessary string manipulation. The algorithm processes each character at most once, leading to efficient performance.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Split strings and compare segments | O(n + m) | O(n + m) |
| Two-pointer parsing without extra arrays | O(n + m) | O(1) |
Naresh Gupta
Use these hints if you're stuck. Try solving on your own first.
You can use two pointers for each version string to traverse them together while comparing the corresponding segments.
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.
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.
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.
1public class Solution {
2 public int CompareVersion(string version1, string version2) {
3 string[] v1 = version1.Split('.');
4 string[] v2 = version2.Split('.');
5
6 int length = Math.Max(v1.Length, v2.Length);
7 for (int i = 0; i < length; i++) {
8 int num1 = i < v1.Length ? int.Parse(v1[i]) : 0;
9 int num2 = i < v2.Length ? int.Parse(v2[i]) : 0;
10 if (num1 < num2) return -1;
11 if (num1 > num2) return 1;
12 }
13
return 0;
}
}The C# solution employs the Split method to separate version strings into components. Each segment is parsed into integers for comparison within a loop.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, string parsing and comparison problems like Compare Version Numbers frequently appear in technical interviews. They test attention to edge cases such as leading zeros, varying segment lengths, and efficient string traversal.
If one version has fewer segments, treat the missing revisions as 0. For example, "1.0" and "1.0.0" should be considered equal because the extra segment contributes no additional value.
No complex data structure is required for this problem. Basic string processing with pointers or arrays from string splitting is sufficient to extract and compare each revision number.
The optimal approach is to compare each revision segment individually by parsing integers between dots. A two-pointer technique can scan both strings and build numbers on the fly, comparing them without creating extra arrays.
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.