题解 | #比较版本号#

方法一：分割后比较
核心思想：可以将需要比较的两个版本号按拆分为块，逐块进行比较，根据比较结果进行返回。
注意：可能出现两个版本号块数不同，此时将较短版本号后续块中字符视为0。
图示：

核心代码：

class Solution {
public:
    //用于拆分版本号的辅助函数
    void helper(vector<int>& nums, string& version) {
        int n = version.length(), num = 0;
        for(int i = 0; i < n; ++i) {
            if(version[i] == '.') {//以“.”为切分标识
                nums.push_back(num);
                num = 0;
            } else {
                num = num * 10 + (version[i] - '0');
            }
        }
        nums.push_back(num);
    }

    int compare(string version1, string version2) {
        vector<int> nums1, nums2; //用于存储分割后字符串（以数字形式）
        helper(nums1, version1);
        helper(nums2, version2);
        int n1 = nums1.size(), n2 = nums2.size();
        int p1 = 0, p2 = 0;
        //对切分后数组进行比较
        for(int i = 0; i < max(n1, n2); ++i) {
            p1 = i < n1 ? nums1[i] : 0;//如果长度大于数组长度，字符视为0
            p2 = i < n2 ? nums2[i] : 0;
            if(p1 > p2) {
                return 1;
            } else if(p1 < p2) {
                return -1;
            }
        }
        return 0;
    }
};

复杂度分析：
时间复杂度：,其中m, n分别为两个字符串长度。需要遍历两个字符串各一次，之后对数组进行遍历
空间复杂度：，需要开辟两个数组切分后的块

方法二：双指针
核心思想：
方法一需要使用两个数组存储切分后的块，也可以采用双指针的方法，进行解析和比较，省去存储切分后的块的开销
核心代码：

class Solution {
public:
    int compare(string version1, string version2) {
        int len1 = 0, len2 = 0, n1 = version1.length(), n2 = version2.length();
        while(len1 < n1 || len2 < n2) {
            int num1 = 0, num2 = 0;//初始化为0
            while(len1 < n1 && version1[len1] != '.') {
            //此时如果长度较短的字符串到了尽头，不进入循环，对应数字为0
                num1 = num1 * 10 + (version1[len1++] - '0');
            }
            while(len2 < n2 && version2[len2] != '.') {
                num2 = num2 * 10 + (version2[len2++] - '0');
            }
            if(num1 > num2) {
                return 1;
            } else if(num1 < num2) {
                return -1;
            }
            //指针后移
            ++len1;
            ++len2;
        }
        return 0;
    }
};

复杂度分析：
时间复杂度：,其中m, n分别为两个字符串长度。需要遍历到较长字符串的尽头
空间复杂度：，只用到了常数个变量