Compare Version Numbers

XXX. Compare Version Numbers

String Manipulation

Comparison

Problem Statement:

Given two version numbers, version1 and version2, compare them. Version numbers consist of one or more levels separated by a dot ("."). Each level contains only digits. Compare the versions based on their levels, starting from the first. If one version has fewer levels, treat the missing levels as 0.

Return:

• 1 if version1 > version2.
• -1 if version1 < version2.
• 0 if version1 == version2.

Algorithm:

The algorithm splits both version numbers into their respective levels using the dot character as a delimiter. It then compares corresponding levels as integers:

1. Split version1 and version2 into arrays of levels using String.split("\\.").
2. Iterate through the maximum length of the two arrays. For each level:
   • If a level is missing, treat it as 0.
   • Convert the level strings to integers and compare them.
   • If the integers are not equal, return the comparison result.
3. If all levels are equal, return 0.

Complexity:

Time Complexity: O(max(n, m)), where n and m are the number of levels in version1 and version2, respectively. Each level is processed once.
Space Complexity: O(max(n, m)), for the arrays of levels.

Java Implementation:

public int compareVersion(String version1, String version2) {
    // Split version strings into levels
    String[] levels1 = version1.split("\\.");
    String[] levels2 = version2.split("\\.");

    // Determine the maximum number of levels to compare
    int length = Math.max(levels1.length, levels2.length);
    
    for (int i = 0; i < length; i++) {
        // Parse levels as integers, treating missing levels as 0
        Integer v1 = i < levels1.length ? Integer.parseInt(levels1[i]) : 0;
        Integer v2 = i < levels2.length ? Integer.parseInt(levels2[i]) : 0;
        
        // Compare current levels
        int compare = v1.compareTo(v2);
        if (compare != 0) return compare;
    }
    
    // All levels are equal
    return 0;
}