一、题目描述LeetCode 上有一道经典字符串题比较版本号。题目大意是给你两个版本号字符串version1和version2请你比较它们的大小。版本号由若干个修订号组成修订号之间用点号.分隔。例如1.0.3 1.02.4 2.1每一个被.分开的部分叫做一个修订号。题目要求从左到右依次比较每一个修订号。修订号比较时要转换成整数。前导零需要忽略。如果某个版本号的修订号数量较少那么缺失的部分当成0。如果version1 version2返回1。如果version1 version2返回-1。如果二者相等返回0。二、先看几个例子示例一version1 1.01 version2 1.001表面上看01 001字符串不一样。但是题目说修订号要转换成整数并忽略前导零。所以Number(01) 1 Number(001) 1因此1.01 和 1.001 相等返回0示例二version1 1.0 version2 1.0.0拆开后version1 [1, 0] version2 [1, 0, 0]version1少了最后一个修订号。题目规定缺失的修订号当成0。所以可以理解成version1 [1, 0, 0] version2 [1, 0, 0]因此二者相等返回0示例三version1 1.0.1 version2 1拆开后version1 [1, 0, 1] version2 [1]逐段比较第一段1 1 第二段0 0 第三段1 0所以1.0.1 1返回1三、为什么不能直接比较字符串很多初学者看到这个题第一反应可能是直接比较if (version1 version2) return 1; if (version1 version2) return -1; return 0;这样是不对的。比如version1 1.10 version2 1.2从版本号规则来看第一段1 1 第二段10 2所以1.10 1.2但是如果按字符串比较10和2会按照字符顺序比较。字符串10的第一个字符是1字符串2的第一个字符是2。因为1 2所以字符串比较会错误地认为10 2这显然不符合版本号比较规则。所以这道题不能直接比较整个字符串必须按照.分割出来的每一段数字进行比较。四、普通解法split 分割最容易想到的解法是使用split(.)把两个版本号拆成数组。找到两个数组中较长的长度。从左到右逐段比较。每一段都转成数字。如果某个数组没有当前段就当成0。代码如下var compareVersion function(version1, version2) { const arr1 version1.split(.); const arr2 version2.split(.); const len Math.max(arr1.length, arr2.length); for (let i 0; i len; i) { const num1 Number(arr1[i] || 0); const num2 Number(arr2[i] || 0); if (num1 num2) { return 1; } if (num1 num2) { return -1; } } return 0; };这段代码比较直观适合刚开始理解这道题。五、split 解法的问题split解法虽然简单但是它会创建额外数组。比如1.02.003.4.split(.)会得到[1, 02, 003, 4]也就是说它会先把整个字符串全部拆开然后再比较。但是实际上比较版本号的时候并不一定需要知道后面所有修订号。比如version1 2.0.0.0.0 version2 1.999.999.999第一段比较2 1结果已经确定了。后面的内容根本不需要再看。所以split解法有一个缺点空间复杂度是 O(n m)其中n和m分别是两个版本号字符串的长度。那么有没有办法不创建数组一边扫描一边比较呢答案就是双指针。六、双指针解法核心思想双指针解法的核心是不提前拆分字符串而是用两个指针分别扫描version1和version2每次取出当前修订号进行比较。定义两个指针let i 0; let j 0;其中i 指向 version1 当前扫描的位置 j 指向 version2 当前扫描的位置每一轮循环中我们分别从version1和version2中读取一个修订号。比如version1 1.01.3 version2 1.001.2第一轮读取version1 当前修订号1 version2 当前修订号1第二轮读取version1 当前修订号01转换成整数是 1 version2 当前修订号001转换成整数是 1第三轮读取version1 当前修订号3 version2 当前修订号2发现3 2所以直接返回1七、如何一边扫描一边把字符串转成数字假设当前要读取这一段123我们可以从左到右扫描。初始num 0读到字符1num num * 10 1 num 0 * 10 1 num 1读到字符2num num * 10 2 num 1 * 10 2 num 12读到字符3num num * 10 3 num 12 * 10 3 num 123所以代码可以这样写num num * 10 Number(version[i]);这就是手动把字符串数字转换成整数。八、为什么前导零会自动被忽略比如当前修订号是001初始num 0读到第一个0num 0 * 10 0 num 0读到第二个0num 0 * 10 0 num 0读到1num 0 * 10 1 num 1所以001最后得到的数字就是1。前导零自然就被忽略了。这也是双指针解法非常巧妙的地方。九、双指针完整代码var compareVersion function(version1, version2) { let i 0; let j 0; const n version1.length; const m version2.length; while (i n || j m) { let num1 0; let num2 0; while (i n version1[i] ! .) { num1 num1 * 10 Number(version1[i]); i; } while (j m version2[j] ! .) { num2 num2 * 10 Number(version2[j]); j; } if (num1 num2) { return 1; } if (num1 num2) { return -1; } i; j; } return 0; };十、代码详细讲解1. 初始化两个指针let i 0; let j 0;i用来遍历version1。j用来遍历version2。它们都从字符串的第一个字符开始扫描。2. 保存字符串长度const n version1.length; const m version2.length;后面循环时需要判断指针有没有越界所以先保存两个字符串的长度。3. 外层循环为什么用||while (i n || j m) {这里一定要注意是||不是。原因是只要有一个版本号还没扫描完就应该继续比较。比如version1 1.0.1 version2 1当version2扫描完之后version1后面还有.0.1这些内容仍然需要和version2缺失的修订号0比较。如果写成while (i n j m)那么只要有一个字符串结束循环就停止了。这样会错误地认为1.0.1 和 1 相等但实际上1.0.1 1所以外层循环必须写成while (i n || j m)4. 每一轮重新计算当前修订号let num1 0; let num2 0;每次进入外层循环都表示要比较一个新的修订号。所以num1和num2都要重新初始化为0。5. 读取 version1 当前修订号while (i n version1[i] ! .) { num1 num1 * 10 Number(version1[i]); i; }这段代码的作用是从当前位置i开始一直读取到下一个.为止。例如version1 1.02.3第一轮时i指向1.02.3 ^ i读取到数字1后i继续往后走。当i指向.时1.02.3 ^ i说明当前修订号已经读完了。于是内部循环停止。此时num1就是当前修订号的整数值。6. 读取 version2 当前修订号while (j m version2[j] ! .) { num2 num2 * 10 Number(version2[j]); j; }这段逻辑和version1完全一样。它负责读取version2的当前修订号。7. 比较当前两个修订号if (num1 num2) { return 1; } if (num1 num2) { return -1; }版本号比较是从左到右逐级比较。只要当前修订号已经分出大小整个版本号的大小就确定了。例如version1 2.0.0 version2 1.999.999第一段2 1所以直接返回1。后面的0.0 999.999已经不需要再比较了。8. 为什么最后要i和ji; j;内部循环停止时指针通常会停在.的位置。比如version1 1.02.3读取完第一段1后i停在1.02.3 ^ i下一轮我们不希望从.开始读而是希望跳过这个点从下一个数字开始读。所以需要i;这样i就移动到1.02.3 ^ ij的作用也是一样。9. 字符串结束后继续i会不会出错不会。因为读取修订号的时候有判断while (i n version1[i] ! .)如果i已经超过了字符串范围i n不成立就不会进入循环。此时num1 0刚好表示缺失的修订号为0。比如version1 1 version2 1.0.0第一轮比较num1 1 num2 1相等。之后version1已经结束了。第二轮num1 0 num2 0第三轮num1 0 num2 0最后所有修订号都相等所以返回0这正好符合题意。十一、完整执行过程示例以这个例子为例version1 1.0.1 version2 1初始i 0 j 0第一轮读取version1当前修订号num1 1读取version2当前修订号num2 1比较num1 num2继续下一轮。第二轮version1读取到第二段num1 0version2已经结束缺失部分当成0num2 0比较num1 num2继续下一轮。第三轮version1读取到第三段num1 1version2仍然已经结束缺失部分当成0num2 0比较num1 num2所以返回1说明1.0.1 1十二、复杂度分析设version1的长度为nversion2的长度为m。双指针扫描过程中每个字符最多被访问一次。所以时间复杂度是O(n m)整个过程中只使用了i j num1 num2 n m这些变量没有创建额外数组。所以空间复杂度是O(1)十三、split 解法和双指针解法对比解法思路时间复杂度空间复杂度优点缺点split 解法先按.分割成数组再逐段比较O(n m)O(n m)简单直观需要额外数组双指针解法一边扫描一边读取当前修订号O(n m)O(1)空间更优代码理解稍难实际刷题时如果只是想快速通过split解法完全可以。但如果想写出更优解或者面试时体现对空间复杂度的优化双指针解法更合适。十四、这道题的关键点总结这道题看起来是字符串比较实际上考察的是能不能正确理解版本号的比较规则。能不能避免直接字符串比较的错误。能不能处理前导零。能不能处理版本号长度不一致的情况。能不能用双指针优化空间复杂度。最终双指针解法可以概括为一句话用两个指针分别扫描两个版本号字符串每次读取一个修订号转成整数后比较如果当前修订号不同立即返回结果如果全部相同则返回 0。十五、最终推荐代码var compareVersion function(version1, version2) { let i 0; let j 0; const n version1.length; const m version2.length; while (i n || j m) { let num1 0; let num2 0; while (i n version1[i] ! .) { num1 num1 * 10 Number(version1[i]); i; } while (j m version2[j] ! .) { num2 num2 * 10 Number(version2[j]); j; } if (num1 num2) { return 1; } if (num1 num2) { return -1; } i; j; } return 0; };这份代码的优势是不需要split创建数组直接在原字符串上扫描空间复杂度为O(1)是这道题更优雅的写法。
LeetCode 比较版本号：从 split 解法到双指针优化，彻底讲懂这道题
一、题目描述LeetCode 上有一道经典字符串题比较版本号。题目大意是给你两个版本号字符串version1和version2请你比较它们的大小。版本号由若干个修订号组成修订号之间用点号.分隔。例如1.0.3 1.02.4 2.1每一个被.分开的部分叫做一个修订号。题目要求从左到右依次比较每一个修订号。修订号比较时要转换成整数。前导零需要忽略。如果某个版本号的修订号数量较少那么缺失的部分当成0。如果version1 version2返回1。如果version1 version2返回-1。如果二者相等返回0。二、先看几个例子示例一version1 1.01 version2 1.001表面上看01 001字符串不一样。但是题目说修订号要转换成整数并忽略前导零。所以Number(01) 1 Number(001) 1因此1.01 和 1.001 相等返回0示例二version1 1.0 version2 1.0.0拆开后version1 [1, 0] version2 [1, 0, 0]version1少了最后一个修订号。题目规定缺失的修订号当成0。所以可以理解成version1 [1, 0, 0] version2 [1, 0, 0]因此二者相等返回0示例三version1 1.0.1 version2 1拆开后version1 [1, 0, 1] version2 [1]逐段比较第一段1 1 第二段0 0 第三段1 0所以1.0.1 1返回1三、为什么不能直接比较字符串很多初学者看到这个题第一反应可能是直接比较if (version1 version2) return 1; if (version1 version2) return -1; return 0;这样是不对的。比如version1 1.10 version2 1.2从版本号规则来看第一段1 1 第二段10 2所以1.10 1.2但是如果按字符串比较10和2会按照字符顺序比较。字符串10的第一个字符是1字符串2的第一个字符是2。因为1 2所以字符串比较会错误地认为10 2这显然不符合版本号比较规则。所以这道题不能直接比较整个字符串必须按照.分割出来的每一段数字进行比较。四、普通解法split 分割最容易想到的解法是使用split(.)把两个版本号拆成数组。找到两个数组中较长的长度。从左到右逐段比较。每一段都转成数字。如果某个数组没有当前段就当成0。代码如下var compareVersion function(version1, version2) { const arr1 version1.split(.); const arr2 version2.split(.); const len Math.max(arr1.length, arr2.length); for (let i 0; i len; i) { const num1 Number(arr1[i] || 0); const num2 Number(arr2[i] || 0); if (num1 num2) { return 1; } if (num1 num2) { return -1; } } return 0; };这段代码比较直观适合刚开始理解这道题。五、split 解法的问题split解法虽然简单但是它会创建额外数组。比如1.02.003.4.split(.)会得到[1, 02, 003, 4]也就是说它会先把整个字符串全部拆开然后再比较。但是实际上比较版本号的时候并不一定需要知道后面所有修订号。比如version1 2.0.0.0.0 version2 1.999.999.999第一段比较2 1结果已经确定了。后面的内容根本不需要再看。所以split解法有一个缺点空间复杂度是 O(n m)其中n和m分别是两个版本号字符串的长度。那么有没有办法不创建数组一边扫描一边比较呢答案就是双指针。六、双指针解法核心思想双指针解法的核心是不提前拆分字符串而是用两个指针分别扫描version1和version2每次取出当前修订号进行比较。定义两个指针let i 0; let j 0;其中i 指向 version1 当前扫描的位置 j 指向 version2 当前扫描的位置每一轮循环中我们分别从version1和version2中读取一个修订号。比如version1 1.01.3 version2 1.001.2第一轮读取version1 当前修订号1 version2 当前修订号1第二轮读取version1 当前修订号01转换成整数是 1 version2 当前修订号001转换成整数是 1第三轮读取version1 当前修订号3 version2 当前修订号2发现3 2所以直接返回1七、如何一边扫描一边把字符串转成数字假设当前要读取这一段123我们可以从左到右扫描。初始num 0读到字符1num num * 10 1 num 0 * 10 1 num 1读到字符2num num * 10 2 num 1 * 10 2 num 12读到字符3num num * 10 3 num 12 * 10 3 num 123所以代码可以这样写num num * 10 Number(version[i]);这就是手动把字符串数字转换成整数。八、为什么前导零会自动被忽略比如当前修订号是001初始num 0读到第一个0num 0 * 10 0 num 0读到第二个0num 0 * 10 0 num 0读到1num 0 * 10 1 num 1所以001最后得到的数字就是1。前导零自然就被忽略了。这也是双指针解法非常巧妙的地方。九、双指针完整代码var compareVersion function(version1, version2) { let i 0; let j 0; const n version1.length; const m version2.length; while (i n || j m) { let num1 0; let num2 0; while (i n version1[i] ! .) { num1 num1 * 10 Number(version1[i]); i; } while (j m version2[j] ! .) { num2 num2 * 10 Number(version2[j]); j; } if (num1 num2) { return 1; } if (num1 num2) { return -1; } i; j; } return 0; };十、代码详细讲解1. 初始化两个指针let i 0; let j 0;i用来遍历version1。j用来遍历version2。它们都从字符串的第一个字符开始扫描。2. 保存字符串长度const n version1.length; const m version2.length;后面循环时需要判断指针有没有越界所以先保存两个字符串的长度。3. 外层循环为什么用||while (i n || j m) {这里一定要注意是||不是。原因是只要有一个版本号还没扫描完就应该继续比较。比如version1 1.0.1 version2 1当version2扫描完之后version1后面还有.0.1这些内容仍然需要和version2缺失的修订号0比较。如果写成while (i n j m)那么只要有一个字符串结束循环就停止了。这样会错误地认为1.0.1 和 1 相等但实际上1.0.1 1所以外层循环必须写成while (i n || j m)4. 每一轮重新计算当前修订号let num1 0; let num2 0;每次进入外层循环都表示要比较一个新的修订号。所以num1和num2都要重新初始化为0。5. 读取 version1 当前修订号while (i n version1[i] ! .) { num1 num1 * 10 Number(version1[i]); i; }这段代码的作用是从当前位置i开始一直读取到下一个.为止。例如version1 1.02.3第一轮时i指向1.02.3 ^ i读取到数字1后i继续往后走。当i指向.时1.02.3 ^ i说明当前修订号已经读完了。于是内部循环停止。此时num1就是当前修订号的整数值。6. 读取 version2 当前修订号while (j m version2[j] ! .) { num2 num2 * 10 Number(version2[j]); j; }这段逻辑和version1完全一样。它负责读取version2的当前修订号。7. 比较当前两个修订号if (num1 num2) { return 1; } if (num1 num2) { return -1; }版本号比较是从左到右逐级比较。只要当前修订号已经分出大小整个版本号的大小就确定了。例如version1 2.0.0 version2 1.999.999第一段2 1所以直接返回1。后面的0.0 999.999已经不需要再比较了。8. 为什么最后要i和ji; j;内部循环停止时指针通常会停在.的位置。比如version1 1.02.3读取完第一段1后i停在1.02.3 ^ i下一轮我们不希望从.开始读而是希望跳过这个点从下一个数字开始读。所以需要i;这样i就移动到1.02.3 ^ ij的作用也是一样。9. 字符串结束后继续i会不会出错不会。因为读取修订号的时候有判断while (i n version1[i] ! .)如果i已经超过了字符串范围i n不成立就不会进入循环。此时num1 0刚好表示缺失的修订号为0。比如version1 1 version2 1.0.0第一轮比较num1 1 num2 1相等。之后version1已经结束了。第二轮num1 0 num2 0第三轮num1 0 num2 0最后所有修订号都相等所以返回0这正好符合题意。十一、完整执行过程示例以这个例子为例version1 1.0.1 version2 1初始i 0 j 0第一轮读取version1当前修订号num1 1读取version2当前修订号num2 1比较num1 num2继续下一轮。第二轮version1读取到第二段num1 0version2已经结束缺失部分当成0num2 0比较num1 num2继续下一轮。第三轮version1读取到第三段num1 1version2仍然已经结束缺失部分当成0num2 0比较num1 num2所以返回1说明1.0.1 1十二、复杂度分析设version1的长度为nversion2的长度为m。双指针扫描过程中每个字符最多被访问一次。所以时间复杂度是O(n m)整个过程中只使用了i j num1 num2 n m这些变量没有创建额外数组。所以空间复杂度是O(1)十三、split 解法和双指针解法对比解法思路时间复杂度空间复杂度优点缺点split 解法先按.分割成数组再逐段比较O(n m)O(n m)简单直观需要额外数组双指针解法一边扫描一边读取当前修订号O(n m)O(1)空间更优代码理解稍难实际刷题时如果只是想快速通过split解法完全可以。但如果想写出更优解或者面试时体现对空间复杂度的优化双指针解法更合适。十四、这道题的关键点总结这道题看起来是字符串比较实际上考察的是能不能正确理解版本号的比较规则。能不能避免直接字符串比较的错误。能不能处理前导零。能不能处理版本号长度不一致的情况。能不能用双指针优化空间复杂度。最终双指针解法可以概括为一句话用两个指针分别扫描两个版本号字符串每次读取一个修订号转成整数后比较如果当前修订号不同立即返回结果如果全部相同则返回 0。十五、最终推荐代码var compareVersion function(version1, version2) { let i 0; let j 0; const n version1.length; const m version2.length; while (i n || j m) { let num1 0; let num2 0; while (i n version1[i] ! .) { num1 num1 * 10 Number(version1[i]); i; } while (j m version2[j] ! .) { num2 num2 * 10 Number(version2[j]); j; } if (num1 num2) { return 1; } if (num1 num2) { return -1; } i; j; } return 0; };这份代码的优势是不需要split创建数组直接在原字符串上扫描空间复杂度为O(1)是这道题更优雅的写法。
