165.Compare-Version-Numbers.md

165. Compare Version Numbers

---

题目地址

https://leetcode.com/problems/compare-version-numbers/

题目描述

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.

For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

You may assume the default revision number for each level of a version number to be 0. For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.

Example 1:
Input: version1 = "0.1", version2 = "1.1"
Output: -1

Example 2:
Input: version1 = "1.0.1", version2 = "1"
Output: 1

Example 3:
Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: -1

Example 4:
Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both “01” and “001" represent the same number “1”

Example 5:
Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: The first version number does not have a third level revision number, which means its third level revision number is default to "0"
 
Note:
Version strings are composed of numeric strings separated by dots . and this numeric strings may have leading zeroes.
Version strings do not start or end with dots, and they will not be two consecutive dots.

代码

Approach 1: Split + Parse, Two Pass, Linear Space

Complexity Analysis

• Time complexity : O(N+M+max(N,M)), where N and M are lengths of input strings.
• Space complexity : O(N+M) to store arrays nums1 and nums2.

class Solution {
    public int compareVersion(String version1, String version2) {
    	String[] nums1 = version1.split("\\.");
      String[] nums2 = version2.split("\\.");
      int n1 = nums1.length;
      int n2 = nums2.length;
      
      int i1, i2;
      for (int i = 0; i < Math.max(n1, n2); i++) {
        i1 = i < n1 ? Integer.parseInt(nums1[i]) : 0;
        i2 = i < n2 ? Integer.parseInt(nums2[i]) : 0;
        if (i1 != i2) {
          return i1 > i2 ? 1 : -1;
        }
      }
      
      return 0;
    }
}

Approach #2: Two Pointers, One Pass, Constant Space

Complexity Analysis

• Time complexity : O(max(N,M)), where Nand M are lengths of the input strings respectively. It's a one-pass solution.
• Space complexity :O(1), since we don't use any additional data structure.

class Solution {
  public Pair<Integer, Integer> getNextChunk(String version, int n, int p) {
    // if pointer is set to the end of string
    // return 0
    if (p > n - 1) {
      return new Pair(0, p);
    }
    // find the end of chunk
    int i, pEnd = p;
    while (pEnd < n && version.charAt(pEnd) != '.') {
      ++pEnd;
    }
    // retrieve the chunk
    if (pEnd != n - 1) {
      i = Integer.parseInt(version.substring(p, pEnd));
    } else {
      i = Integer.parseInt(version.substring(p, n));
    }
    // find the beginning of next chunk
    p = pEnd + 1;

    return new Pair(i, p);
  }

  public int compareVersion(String version1, String version2) {
    int p1 = 0, p2 = 0;
    int n1 = version1.length(), n2 = version2.length();

    // compare versions
    int i1, i2;
    Pair<Integer, Integer> pair;
    while (p1 < n1 || p2 < n2) {
      pair = getNextChunk(version1, n1, p1);
      i1 = pair.getKey();
      p1 = pair.getValue();

      pair = getNextChunk(version2, n2, p2);
      i2 = pair.getKey();
      p2 = pair.getValue();
      if (i1 != i2) {
        return i1 > i2 ? 1 : -1;
      }
    }
    // the versions are equal
    return 0;
  }
}