leetcode 165 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.

Here is an example of version numbers ordering: 0.1 < 1.1 < 1.2 < 13.37

解决方案： The main idea is very simple and the code consists of three phases: 1.When version1 and version2 are not finished, compare the value of corresponding string before dot. 2.If version1 is finished, check whether remaining version2 contains string not equal to 0 3.If version2 is finished, check whether remaining version1 contains string not equal to 0

Example1: version1==”11.22.33”, version2==”11.22.22”. 11 == 11; 22 == 22; 33 > 22; return 1.

Example2: version1==”11.22.33”, version2==”11.22.33”. 11 == 11; 22 == 22; 33 == 33; return 0.

Example3: version1==”11.22.33”, version2==”11.22.33.00.00”. 11 == 11; 22 == 22; 33 == 33; remaining version2 equals to 0; return 0.

Example4: version1==”11.22.33.00.01”, version2==”11.22.33”. 11 == 11; 22 == 22; 33 == 33; remaining version1 contains 01; return 1.

这里写图片描述

class Solution {
public:
    int compareVersion(string version1, string version2)
    {
        int i = 0;
        int j = 0;
        int n1 = version1.size();
        int n2 = version2.size();

        int num1 = 0;
        int num2 = 0;

        while(i < n1 || j < n2)
        { 
            while(i<n1 && version1[i]!='.')
            {
                num1 = num1*10 + (version1[i]-'0');
                i++;
            }

            while(j<n2 && version2[j]!='.')
            {
                num2 = num2*10 + (version2[j]-'0');
                j++;
            }

            if(num1>num2) return 1;

            else if(num1<num2) return -1;

            num1 = 0;
            num2 = 0;

            i++;
            j++;

        }
        return 0;

    }
};

python解决方案：

class Solution:
    # @param a, a string
    # @param b, a string
    # @return a boolean
    def compareVersion(self, version1, version2):
        v1 = version1.split('.')
        v2 = version2.split('.')
        for i in range(max(len(v1), len(v2))):
            gap = (int(v1[i]) if i < len(v1) else 0) - (int(v2[i]) if i < len(v2) else 0)
            if gap != 0:
                return 1 if gap > 0 else -1
        return 0