NUHMAN.com

Introduction

LeetCode 165 requires us to compare two version numbers represented as strings. A version number consists of several non-negative integers separated by dots (.). For example, "1.0" and "1.0.0" are equivalent, while "1.1" is greater than "1.0".

The task is to compare two version numbers and determine if the first is less than, greater than, or equal to the second. We need to return:

• 1 if the first version is greater.
• -1 if the second version is greater.
• 0 if both versions are equal.

Problem Statement

Given two version strings version1 and version2, return:

• 1 if version1 > version2
• -1 if version1 < version2
• 0 if they are equal.

Function Signature:

go

func compareVersion(version1 string, version2 string) int

• Input:
• version1: A string representing the first version.
• version2: A string representing the second version.
• Output:
• An integer indicating the comparison result (1, -1, or 0).

Approach

We need to compare two version numbers. The version numbers may have a different number of segments, and some segments may have leading zeros. We can break down the version numbers into segments (substrings separated by dots), and compare the corresponding segments.

Steps:

1. Split the version strings by the dot (.) separator.
2. Compare the corresponding segments:

• If the segment of version1 is greater, return 1.
• If the segment of version2 is greater, return -1.

1. If one version has more segments than the other, treat the missing segments as 0 and continue comparing.
2. If all segments are equal, return 0.

Time Complexity:

• O(n + m) where n and m are the lengths of version1 and version2, respectively. We are splitting the strings and comparing corresponding segments.

Space Complexity:

• O(n + m) due to the space needed to store the split versions.

Go Implementation

go

import "strings"

func compareVersion(version1 string, version2 string) int {
    // Split both version strings by "."
    parts1 := strings.Split(version1, ".")
    parts2 := strings.Split(version2, ".")
    
    // Compare each corresponding part
    maxLength := max(len(parts1), len(parts2))
    
    for i := 0; i < maxLength; i++ {
        // Get the current part or treat it as "0" if out of bounds
        v1 := 0
        v2 := 0
        
        if i < len(parts1) {
            v1 = atoi(parts1[i])
        }
        
        if i < len(parts2) {
            v2 = atoi(parts2[i])
        }
        
        // Compare the parts
        if v1 > v2 {
            return 1
        } else if v1 < v2 {
            return -1
        }
    }
    
    // If all parts are equal, return 0
    return 0
}

// Helper function to convert string to integer
func atoi(str string) int {
    result := 0
    for i := 0; i < len(str); i++ {
        result = result*10 + int(str[i]-'0')
    }
    return result
}

// Helper function to return maximum of two integers
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation of the Code:

1. Split the Version Strings:

• We use strings.Split(version1, ".") and strings.Split(version2, ".") to split both version strings into their corresponding components (substrings separated by dots).

2. Compare the Segments:

• We calculate the maximum length of the two arrays parts1 and parts2 to make sure we compare all the segments, including considering missing segments as 0.
• We iterate through each segment, converting them to integers using the helper function atoi. This allows us to properly handle cases like "01" and "1" (treating them as equal).

3. Compare Integer Values:

• If the integer value of the current segment from version1 is greater than the corresponding segment from version2, we return 1.
• If it's less, we return -1.
• If all segments are equal, we return 0.

4. Helper Functions:

• atoi: This helper function converts a string representing a number to an integer, considering the string's value.
• max: This helper function returns the maximum of two integers, used to handle versions with different lengths.

Example

Example 1:

go

version1 := "1.01"
version2 := "1.001"
result := compareVersion(version1, version2)
fmt.Println(result) // Output: 0

Explanation:

• The versions are equivalent after ignoring leading zeros. Both 1.01 and 1.001 are effectively 1.1, so the result is 0.

Example 2:

go

version1 := "1.0"
version2 := "1.0.0"
result := compareVersion(version1, version2)
fmt.Println(result) // Output: 0

Explanation:

• Both 1.0 and 1.0.0 are equivalent, so the result is 0.

Example 3:

go

version1 := "0.1"
version2 := "1.1"
result := compareVersion(version1, version2)
fmt.Println(result) // Output: -1

Explanation:

• 0.1 is less than 1.1, so the result is -1.

Example 4:

go

version1 := "1.0.1"
version2 := "1"
result := compareVersion(version1, version2)
fmt.Println(result) // Output: 1

Explanation:

• 1.0.1 is greater than 1, so the result is 1.

Conclusion

LeetCode 165 is a problem that involves comparing version numbers in string format. By splitting the version strings into segments, converting them to integers, and comparing them accordingly, we can efficiently solve the problem. This solution handles all edge cases, including different lengths of version strings, leading zeros, and missing segments.