165. Compare Version Numbers

Description

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:

• If version1 < version2, return -1.
• If version1 > version2, return 1.
• Otherwise, return 0.

 

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 <= 500
• version1 and version2 only contain digits and '.'.
• version1 and version2 are valid version numbers.
• All the given revisions in version1 and version2 can be stored in a 32-bit integer.

Solutions

Solution 1: Two Pointers

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.

Python3JavaC++GoTypeScriptRustC#

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        m, n = len(version1), len(version2)
        i = j = 0
        while i < m or j < n:
            a = b = 0
            while i < m and version1[i] != '.':
                a = a * 10 + int(version1[i])
                i += 1
            while j < n and version2[j] != '.':
                b = b * 10 + int(version2[j])
                j += 1
            if a != b:
                return -1 if a < b else 1
            i, j = i + 1, j + 1
        return 0

class Solution {
    public int compareVersion(String version1, String version2) {
        int m = version1.length(), n = version2.length();
        for (int i = 0, j = 0; i < m || j < n; ++i, ++j) {
            int a = 0, b = 0;
            while (i < m && version1.charAt(i) != '.') {
                a = a * 10 + (version1.charAt(i++) - '0');
            }
            while (j < n && version2.charAt(j) != '.') {
                b = b * 10 + (version2.charAt(j++) - '0');
            }
            if (a != b) {
                return a < b ? -1 : 1;
            }
        }
        return 0;
    }
}

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int m = version1.size(), n = version2.size();
        for (int i = 0, j = 0; i < m || j < n; ++i, ++j) {
            int a = 0, b = 0;
            while (i < m && version1[i] != '.') {
                a = a * 10 + (version1[i++] - '0');
            }
            while (j < n && version2[j] != '.') {
                b = b * 10 + (version2[j++] - '0');
            }
            if (a != b) {
                return a < b ? -1 : 1;
            }
        }
        return 0;
    }
};

func compareVersion(version1 string, version2 string) int {
    m, n := len(version1), len(version2)
    for i, j := 0, 0; i < m || j < n; i, j = i+1, j+1 {
        var a, b int
        for i < m && version1[i] != '.' {
            a = a*10 + int(version1[i]-'0')
            i++
        }
        for j < n && version2[j] != '.' {
            b = b*10 + int(version2[j]-'0')
            j++
        }
        if a < b {
            return -1
        }
        if a > b {
            return 1
        }
    }
    return 0
}

function compareVersion(version1: string, version2: string): number {
    const [m, n] = [version1.length, version2.length];
    let [i, j] = [0, 0];
    while (i < m || j < n) {
        let [a, b] = [0, 0];
        while (i < m && version1[i] !== '.') {
            a = a * 10 + +version1[i];
            i++;
        }
        while (j < n && version2[j] !== '.') {
            b = b * 10 + +version2[j];
            j++;
        }
        if (a !== b) {
            return a < b ? -1 : 1;
        }
        i++;
        j++;
    }
    return 0;
}

impl Solution {
    pub fn compare_version(version1: String, version2: String) -> i32 {
        let (bytes1, bytes2) = (version1.as_bytes(), version2.as_bytes());
        let (m, n) = (bytes1.len(), bytes2.len());
        let (mut i, mut j) = (0, 0);

        while i < m || j < n {
            let mut a = 0;
            let mut b = 0;

            while i < m && bytes1[i] != b'.' {
                a = a * 10 + (bytes1[i] - b'0') as i32;
                i += 1;
            }
            while j < n && bytes2[j] != b'.' {
                b = b * 10 + (bytes2[j] - b'0') as i32;
                j += 1;
            }

            if a != b {
                return if a < b { -1 } else { 1 };
            }

            i += 1;
            j += 1;
        }

        0
    }
}

public class Solution {
    public int CompareVersion(string version1, string version2) {
        int m = version1.Length, n = version2.Length;
        for (int i = 0, j = 0; i < m || j < n; ++i, ++j) {
            int a = 0, b = 0;
            while (i < m && version1[i] != '.') {
                a = a * 10 + (version1[i++] - '0');
            }
            while (j < n && version2[j] != '.') {
                b = b * 10 + (version2[j++] - '0');
            }
            if (a != b) {
                return a < b ? -1 : 1;
            }
        }
        return 0;
    }
}

Comments