Compare Version Numbers

For this question, my overall algorithm was to iterate through all the revisions present in both version1 and version2 and compare them concurrently. To do this, I created a compareRevision function, that compares the revision value for both version1 and version2 and returns:

• -1 if version1 < version2
• 0 if version1 == version2
• 1 if version1 > version2

int compareRevision(string version1, string version2, int& v1Index, int& v2Index) {
    // revision values for version1 and version2 respectively
    int revision1 = 0;
    int revision2 = 0;

    while(v1Index < version1.size() && version1[v1Index] !=  '.') {
        revision1 = revision1 * 10 + (version1[v1Index]-'0');
        ++v1Index;
    }
    while(v2Index < version2.size() && version2[v2Index] !=  '.') {
        revision2 = revision2 * 10 + (version2[v2Index]-'0');
        ++v2Index;
    }

    // increment both indices so they are not stuck on `.`
    ++v1Index;
    ++v2Index;

    if (revision1 < revision2) {
        return -1;
    } else if (revision1 > revision2) {
        return 1;
    } else {
        return 0;
    }
}

Then, I can simply run compareRevision until both v1Index and v2Index exceed the size of version1 and version2 respectively, breaking early if it returns an integer that is not equal to 0. If I reach the end of both version1 and version2 without breaking early, then that implies that both versions are equal and we can simply return 0.

int ans;
while (v1Index < version1.size() || v2Index < version2.size()) {
    ans = compareRevision(version1, version2, v1Index, v2Index);
    if (ans != 0) {
        return ans;
    }
}

return 0;

code

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int v1Index = 0;
        int v2Index = 0;

        int ans;
        while (v1Index < version1.size() || v2Index < version2.size()) {
            ans = compareRevision(version1, version2, v1Index, v2Index);
            if (ans != 0) {
                return ans;
            }
        }

        return 0;
    }
private:
    int compareRevision(string version1, string version2, int& v1Index, int& v2Index) {
        int revision1 = 0;
        int revision2 = 0;
        while(v1Index < version1.size() && version1[v1Index] !=  '.') {
            revision1 = revision1 * 10 + (version1[v1Index]-'0');
            ++v1Index;
        }
        while(v2Index < version2.size() && version2[v2Index] !=  '.') {
            revision2 = revision2 * 10 + (version2[v2Index]-'0');
            ++v2Index;
        }

        ++v1Index;
        ++v2Index;

        if (revision1 < revision2) {
            return -1;
        } else if (revision1 > revision2) {
            return 1;
        } else {
            return 0;
        }
    }
};

complexity

• Time: O(max(m, n)) where m denotes the number of letters inside version1 and n denotes the number of letters inside version2
• Space: O(1)

time taken

• 16 minutes and 41 seconds