Problem

Compare two version numbers version1 and version2. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0. You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used to separate number sequences. Here is an example of version numbers ordering:

1

0.1 < 1.1 < 1.2 < 13.37

Examples

Example 1:

1
2
3

Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both "01" and "001" represent the same integer "1".

Example 2:

1
2
3

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: version1 does not specify revision 2, which means it is treated as "0".

Example 3:

1
2
3

Input: version1 = "0.1", version2 = "1.1"
Output: -1
Explanation: version1's revision 0 is "0", while version2's revision 0 is "1". 0 < 1, so version1 < version2.

Solution

The tricky part of the problem is to handle cases like 1.0 and 1. They should be equal.

Method 1 - Iterative

On way is to split the array, and then compare 1 part of version with another.

Here is a video explanation:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public int compareVersion(String version1, String version2) {
	String[] arr1 = version1.split("\\.");
	String[] arr2 = version2.split("\\.");

	int i = 0;

	while (i < arr1.length || i < arr2.length) {
		if (i < arr1.length && i  <  arr2.length) {
			if (Integer.parseInt(arr1[i])<Integer.parseInt(arr2[i])) {
				return -1;
			} else if (Integer.parseInt(arr1[i]) > Integer.parseInt(arr2[i])) {
				return 1;
			}
		} else if (i < arr1.length) {
			if (Integer.parseInt(arr1[i]) != 0) {
				return 1;
			}
		} else if (i < arr2.length) {
			if (Integer.parseInt(arr2[i]) != 0) {
				return -1;
			}
		}

		i++;
	}

	return 0;
}

Cleaner Code

Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public int compareVersion(String version1, String version2) {
    
    String[] v1 = version1.split("\\.");
    String[] v2 = version2.split("\\.");
    int maxParts = Math.max(v1.length, v2.length);
    for ( int i = 0; i < maxParts; i++ ) {
        int num1 = i < v1.length ? Integer.parseInt( v1[i] ) : 0;
        int num2 = i < v2.length ? Integer.parseInt( v2[i] ) : 0;
        if ( num1 < num2 ) {
            return -1;
        } else if ( num1 > num2 ) {
            return +1;
        }
    } 
    
    return 0;
}

Method 2 - Iterative solution using StringTokenizer

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public int compareVersion(String version1, String version2) {
	StringTokenizer st1 = new StringTokenizer(version1, ".");
	StringTokenizer st2 = new StringTokenizer(version2, ".");
	while (st1.hasMoreTokens() && st2.hasMoreTokens()) {
		int token1 = Integer.parseInt(st1.nextToken());
		int token2 = Integer.parseInt(st2.nextToken());
		if (token1 > token2) {
			return 1;
		} else if (token2 > token1) {
			return -1;
		}
	}

	boolean left = st1.countTokens() > st2.countTokens();
	StringTokenizer remaining = left ? st1: st2;

	while (remaining.hasMoreTokens()){
		if (Integer.parseInt(remaining.nextToken()) > 0) {
			return left ? 1 : -1;
		}
	}

	return 0;
}