LC165. Compare Version Numbers

Approach 1: Optimal

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        if version1 == version2:
            return 0
 
        # Remember this is not just semver. # of parts can be > 3!
        parts1, parts2 = version1.split("."), version2.split(".")
        n1, n2 = len(parts1), len(parts2)
 
        for p1, p2 in zip(map(int, parts1), map(int, parts2)):
            if p1 < p2:
                return -1
            elif p1 > p2:
                return 1
        
        if n1 == n2:
            return 0
        
        remaining = parts1[n2:] if n1 > n2 else parts2[n1:]
 
        for p in map(int, remaining):
            if p > 0:
                return -1 if n1 < n2 else 1
        
        return 0

Complexity

Time: $O(n)$
Space: $O(n)$

Other Languages

Go

NOTE: Like, maybe just do it the straightforward way.

import (
    "bufio"
    "strings"
    "bytes"
)
 
func splitByDot(data []byte, atEof bool) (advance int, token []byte, err error) {
    if atEof && len(data) == 0 {
        return 0, nil, nil
    }
 
    i := bytes.IndexByte(data, '.')
 
    if i == -1 {
        return len(data), data, nil
    }
    
    return i+1, data[:i], nil
}
 
func check(err error) {
    if err != nil {
        panic(err)
    }
}
 
func compareVersion(version1 string, version2 string) int {
    sc1 := bufio.NewScanner(strings.NewReader(version1))
    sc2 := bufio.NewScanner(strings.NewReader(version2))
 
    sc1.Split(splitByDot)
    sc2.Split(splitByDot)
 
    for {
        more1, more2 := sc1.Scan(), sc2.Scan()
 
        if !more1 || !more2 {
            break
        }
 
        p1, err1 := strconv.Atoi(sc1.Text())
        check(err1)
        p2, err2 := strconv.Atoi(sc2.Text())
        check(err2)
 
        if p1 < p2 {
            return -1
        } else if p1 > p2 {
            return 1
        }
    }
 
    if sc1.Text() == "" && sc2.Text() == "" {
        return 0
    }
 
    var scRem *bufio.Scanner
    if sc1.Text() != "" {
        scRem = sc1
    } else {
        scRem = sc2
    }
 
    for {
        p, err := strconv.Atoi(scRem.Text())
        check(err)
 
        if p > 0 {
            if scRem == sc2 {
                return -1
            }
 
            return 1
        }
 
        if !scRem.Scan() {
            break
        }
    }
 
    return 0
}