LeetCode 刷题之字符串【Python实现】

本是古典何须时尚 2023-09-29 19:39 27阅读 0赞

## 1. 字符串反转 ##

**双指针**

class Solution:
        def reverseString(self, s: List[str]) -> None:
            """
            Do not return anything, modify s in-place instead.
            """
            left, right = 0, len(s) - 1
            
            while left < right:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1

## 2. 反转字符串 II ##

[541. 反转字符串 II][541. _ II]

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
    
    如果剩余字符少于 k 个，则将剩余字符全部反转。
    如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
     
    示例 1：
    
    输入：s = "abcdefg", k = 2
    输出："bacdfeg"
    示例 2：
    
    输入：s = "abcd", k = 2
    输出："bacd"
     
    提示：
    
    1 <= s.length <= 104
    s 仅由小写英文组成
    1 <= k <= 104

题解：

class Solution:
        def reverseStr(self, s: str, k: int) -> str:
            p = 0   # 初始坐标
            while p < len(s):
                p2 = p + k  # 第 k 个要反转的字符串坐标
                s = s[:p] + s[p:p2][::-1] + s[p2:]
                p = p + 2 * k   # 坐标往后移动 2k
    
            return s	"abcdefg"
        
    # p = 0	n = 7	k = 2
    # p2 = 2	s=[:0] + s[0:2][::-1] + s[2:]	p = 0 + 2*2	= 4
    # p2 = 4+2=6	s=s[:4] + s[4:6][::-1] + s[6:]	p=4+2*2=8

## 3. 字符串中的第一个唯一字符 ##

[387. 字符串中的第一个唯一字符][387.]

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
    
    示例 1：
    
    输入: s = "leetcode"
    输出: 0
    示例 2:
    
    输入: s = "loveleetcode"
    输出: 2
    示例 3:
    
    输入: s = "aabb"
    输出: -1

题解一：内置函数（`find、count`） 5672 ms

class Solution:
        def firstUniqChar(self, s: str) -> int:
            if len(s) == 1:
                return 0
    
            for i in s:
                if s.count(i) == 1:
                    return s.find(i)
    
            return -1

题解二：哈希表存储字符个数 140 ms

class Solution:
        def firstUniqChar(self, s: str) -> int:
            if len(s) == 1:
                return 0
    
            info = {
        }
            for index, i in enumerate(s):
                if i not in info:
                    info[i] = [index]
                else:
                    info[i].append(index)
    
            for k, v in info.items():
                if len(v) == 1:
                    return v[0]
    
            return -1

题解三：`Counter` 函数 84 ms

class Solution:
        def firstUniqChar(self, s: str) -> int:
            from collections import Counter
            info = Counter(s)
    
            for i, char in enumerate(s):
                if info[char] == 1:
                    return i
    
            return -1

## 4. 最长公共前缀 ##

[14. 最长公共前缀][14.]

编写一个函数来查找字符串数组中的最长公共前缀。
    
    如果不存在公共前缀，返回空字符串 ""。
    
    示例 1：
    
    输入：strs = ["flower","flow","flight"]
    输出："fl"
    示例 2：
    
    输入：strs = ["dog","racecar","car"]
    输出：""
    解释：输入不存在公共前缀。
     
    提示：
    
    1 <= strs.length <= 200
    0 <= strs[i].length <= 200
    strs[i] 仅由小写英文字母组成

题解一：`zip` 函数解包

class Solution:
        def longestCommonPrefix(self, strs: List[str]) -> str:
            if len(strs) == 1:
               return strs[0]
    
            r = ""
            # 利用 zip 解包  [('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]
            for i in zip(*strs):
                if len(set(i)) == 1:
                    r += i[0]
                else:
                    break
    
            return r

题解二：

class Solution:
        def longestCommonPrefix(self, strs: List[str]) -> str:
            if len(strs) == 1:
               return strs[0]
    
            res = strs[0]
            for i in range(1, len(strs)):
                while strs[i].find(res) != 0:
                    res = res[:len(res)-1]
    
            return res

## 5. 颠倒字符串中单词 ##

[151. 颠倒字符串中的单词][151.]

给你一个字符串 s ，颠倒字符串中 单词 的顺序。
    
    单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
    
    返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
    
    注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
    
    示例 1：
    
    输入：s = "the sky is blue"
    输出："blue is sky the"
    示例 2：
    
    输入：s = "  hello world  "
    输出："world hello"
    解释：颠倒后的字符串中不能存在前导空格和尾随空格。
    示例 3：
    
    输入：s = "a good   example"
    输出："example good a"
    解释：如果两个单词间有多余的空格，颠倒后的字符串需要将单词间的空格减少到仅有一个。
     
    
    提示：
    
    1 <= s.length <= 104
    s 包含英文大小写字母、数字和空格 ' '
    s 中 至少存在一个 单词

题解一：

class Solution:
        def reverseWords(self, s: str) -> str:
            strs = [i.strip() for i in s.strip().split(" ") if i]
            strs.reverse()
    
            return " ".join(strs)

题解二：自己实现去除空白、反转

class Solution:
        def trim_spaces(self, s: str) -> list:
            left, right = 0, len(s) - 1
            # 去掉字符串开头的空白字符
            while left <= right and s[left] == ' ':
                left += 1
            
            # 去掉字符串末尾的空白字符
            while left <= right and s[right] == ' ':
                right -= 1
            
            # 将字符串间多余的空白字符去除
            output = []
            while left <= right:
                if s[left] != ' ':
                    output.append(s[left])
                elif output[-1] != ' ':
                    output.append(s[left])
                left += 1
            
            return output
                
        def reverse(self, l: list, left: int, right: int) -> None:
            while left < right:
                l[left], l[right] = l[right], l[left]
                left, right = left + 1, right - 1
                
        def reverse_each_word(self, l: list) -> None:
            n = len(l)
            start = end = 0
            
            while start < n:
                # 循环至单词的末尾
                while end < n and l[end] != ' ':
                    end += 1
                # 翻转单词
                self.reverse(l, start, end - 1)
                # 更新start，去找下一个单词
                start = end + 1
                end += 1
                    
        def reverseWords(self, s: str) -> str:
            l = self.trim_spaces(s)
            
            # 翻转字符串
            self.reverse(l, 0, len(l) - 1)
            
            # 翻转每个单词
            self.reverse_each_word(l)
            
            return ''.join(l)

## 6. 仅反转字母 ##

[917. 仅仅反转字母][917.]

给你一个字符串 s ，根据下述规则反转字符串：
    
    所有非英文字母保留在原有位置。
    所有英文字母（小写或大写）位置反转。
    返回反转后的 s 。
    
    示例 1：
    
    输入：s = "ab-cd"
    输出："dc-ba"
    示例 2：
    
    输入：s = "a-bC-dEf-ghIj"
    输出："j-Ih-gfE-dCba"
    示例 3：
    
    输入：s = "Test1ng-Leet=code-Q!"
    输出："Qedo1ct-eeLg=ntse-T!"
     
    
    提示
    
    1 <= s.length <= 100
    s 仅由 ASCII 值在范围 [33, 122] 的字符组成
    s 不含 '\"' 或 '\\'

题解：双指针

class Solution:
        def reverseOnlyLetters(self, s: str) -> str:
            a = list(s)
            left, right = 0, len(s) - 1
            while left < right:
                
                # 判断有没有扫到非字母
                while left < right and not a[left].isalpha():
                    left += 1
                
                while left < right and not a[right].isalpha():
                    right -= 1
                
                a[left], a[right] = a[right], a[left]
                left += 1
                right -= 1
            return "".join(a)

[541. _ II]: https://leetcode.cn/problems/reverse-string-ii/
[387.]: https://leetcode.cn/problems/first-unique-character-in-a-string/
[14.]: https://leetcode.cn/problems/longest-common-prefix/
[151.]: https://leetcode.cn/problems/reverse-words-in-a-string/
[917.]: https://leetcode.cn/problems/reverse-only-letters/