165_比较版本号

类型：字符串

• 165. 比较版本号 💛

  https://leetcode-cn.com/problems/compare-version-numbers/

  ❓ 比较两个版本号。

  💡 分割后逐一比较

  class Solution:
      def compareVersion(self, version1: str, version2: str) -> int:
          ver_arr1 = version1.split('.')
          ver_arr2 = version2.split('.')
          while ver_arr1 or ver_arr2:
              val1 = int(ver_arr1.pop(0)) if ver_arr1 else 0
              val2 = int(ver_arr2.pop(0)) if ver_arr2 else 0
              if val1 < val2:
                  return -1
              elif val1 > val2:
                  return 1
          return 0

  时间复杂度：O(m + n + max(m, n))，其中 m、n 分别表示两个字符串的长度。总的复杂度包括两个字符串分割各一次，O(m) + O(n)，遍历比较一次，O(max(m, n))。

  空间复杂度：O(m + n)，存储分割后的字符串。

  💡 双指针一次遍历

  上一个方法是先提前把两个版本号给分割好了，然后再遍历比较。为了优化，我们直接在遍历的同时，分割出版本号。

  在此，我们定义一个 get_next_chunk(version, n, p) 函数来获取字符串中的下一个子版本号，以及下一个分割点的起始位置。

  class Solution:
      def get_next_chunk(self, version: str, n: int, p: int) -> List[int]:
          # if pointer is set to the end of string
          # return 0
          if p > n - 1:
              return 0, p
  
          # find the end of chunk
          p_end = p
          while p_end < n and version[p_end] != '.':
              p_end += 1
          # retrieve the chunk
          i = int(version[p:p_end]) if p_end != n - 1 else int(version[p:n])
          # find the beginning of next chunk
          p = p_end + 1
  
          return i, p
  
      def compareVersion(self, version1: str, version2: str) -> int:
          p1 = p2 = 0
          n1, n2 = len(version1), len(version2)
  
          # compare versions
          while p1 < n1 or p2 < n2:
              i1, p1 = self.get_next_chunk(version1, n1, p1)
              i2, p2 = self.get_next_chunk(version2, n2, p2)            
              if i1 != i2:
                  return 1 if i1 > i2 else -1
  
          # the versions are equal
          return 0

  时间复杂度：O(m + n)，空间复杂度：O(1)