字符串 String

165. Compare Version Numbers

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        v1 = version1.split('.')
        v2 = version2.split('.')
        m, n = len(v1), len(v2)
        i, j = 0, 0
        while i < m or j < n:
            a, b = 0, 0
            if i < m:
                a = 0 if (tmp := v1[i].lstrip('0')) == '' else int(tmp)
            if j < n:
                b = 0 if (tmp := v2[j].lstrip('0')) == '' else int(tmp)
            if a < b:
                return -1
            if a > b:
                return 1
            i += 1
            j += 1
        return 0

• 时间复杂度：
• 空间复杂度：

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        m, n = len(version1), len(version2)
        i, j = 0, 0
        while i < m or j < n:
            a = 0
            while i < m and version1[i] != '.':
                a = a*10 + int(version1[i])
                i += 1
            i += 1                               # 跳过'.'

            b = 0
            while j < n and version2[j] != '.':
                b = b*10 + int(version2[j])
                j += 1
            j += 1                               # 跳过'.'

            if a < b:
                return -1
            if a > b:
                return 1
        return 0

• 时间复杂度：
• 空间复杂度：

415. Add Strings

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        if len(num1) < len(num2):
            return self.addStrings(num2, num1)

        res = [''] * len(num1)

        i, j = len(num1) - 1, len(num2) - 1
        carry = 0

        while i >= 0 or j >= 0:
            a = int(num1[i]) if i >= 0 else 0
            b = int(num2[j]) if j >= 0 else 0

            bit, carry = (a + b + carry) % 10, \
                         (a + b + carry) // 10

            res[i] = str(bit)
            i -= 1
            j -= 1

        if carry:
            res = ['1'] + res
        return ''.join(res)

• 时间复杂度：
• 空间复杂度：

394. Decode String

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        res, multiple = '', 0

        for c in s:
            if c == '[':
                stack.append((res, multiple))
                res, multiple = '', 0
            elif c == ']':
                prefix, base = stack.pop()
                res = prefix + base * res
            elif 'a' <= c <= 'z':
                res += c
            elif '0' <= c <= '9':
                multiple = multiple * 10 + int(c)

        return res

• 时间复杂度：

• 空间复杂度：

• 时间复杂度：

• 空间复杂度：

8. String to Integer (atoi)

14. Longest Common Prefix

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        length, n = len(strs[0]), len(strs)
        for j, ch in enumerate(strs[0]):
            for i in range(1, n):
                if j == len(strs[i]) or ch != strs[i][j]:
                    return strs[0][:j]
        return strs[0]

• 时间复杂度：
• 空间复杂度：

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strs.sort()    # 按'字典序'排列
        a, b = strs[0], strs[-1]
        res = []

        for i in range(len(a)):
            if i < len(b) and a[i] == b[i]:
                res.append(a[i])
            else:
                break

        return ''.join(res)

• 时间复杂度：
• 空间复杂度：

151. Reverse Words in a String

手动实现 双端队列

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(reversed(s.split()))

• 时间复杂度：
• 空间复杂度：