2000字范文,分享全网优秀范文,学习好帮手!
2000字范文 > 字符串经典题目(Leetcode题解-Python语言)

字符串经典题目(Leetcode题解-Python语言)

时间:2019-08-13 08:23:52

相关推荐

字符串经典题目(Leetcode题解-Python语言)

344. 反转字符串

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

双指针法,左右各一个指针并且进行字符交换,注意只有列表才可以两两交换,字符串只能够用切片反转 [::-1]

541. 反转字符串 II

class Solution:def reverseStr(self, s: str, k: int) -> str:l = list(s)for i in range(0, len(l), 2*k):l[i:i+k] = l[i:i+k][::-1]return ''.join(l)

按照题目的要求,每次遍历 2k 个字符,然后对前 k 个字符进行反转,字符串反转用 [::-1] 即可。

557. 反转字符串中的单词 III

class Solution:def reverseWords(self, s: str) -> str:return ' '.join(word[::-1] for word in s.split(' '))

用 split 分隔出每个单词,然后用 [::-1] 反转单词,最后再用 join 结合一起即可。

125. 验证回文串

class Solution:def isPalindrome(self, s: str) -> bool:left = 0right = len(s) - 1while left < right:if not s[left].isalnum():left += 1continueif not s[right].isalnum():right -= 1continueif s[left].lower() != s[right].lower():return Falseelse:left += 1right -= 1return True

双指针法,注意指针如果指向的不是数字或者字母就移到下一位,直到都指向数字或字符为止。然后对两个指针指向的字符进行比较,直接转化为小写比较即可(对数字用小写也不会报错),不相等就返回 False,否则就下一位。

345. 反转字符串中的元音字母

class Solution:def reverseVowels(self, s: str) -> str:l = list(s)left = 0right = len(s) - 1vowels = ('a', 'e', 'i', 'o', 'u')while left < right:while left < right and l[left].lower() not in vowels:left += 1while left < right and l[right].lower() not in vowels:right -= 1if left < right:l[left], l[right] = l[right], l[left]left += 1right -= 1return ''.join(l)

还是双指针法,同样的,如果指针指向的不是元音字母就移到下一位,直到是元音字母为止,然后对两个指针指向的字符进行交换即可。

3. 无重复字符的最长子串

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:left = 0right = 0window = dict()ans = 0while right < len(s):if s[right] not in window:window[s[right]] = 1else:window[s[right]] += 1while window[s[right]] > 1:window[s[left]] -= 1left += 1ans = max(ans, right - left + 1)right += 1return ans

双指针 + 滑动窗口,初始时先让 right 指针向右移位,遍历到的字符记录在滑动窗口中,直到有字符是第二次出现,此时就开始让 left 指针右移,直到滑动窗口中没有重复字符为止,对所有的无重复字符子串(滑动窗口)取长度最大值即可。

151. 颠倒字符串中的单词

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

这题用内置函数就是一行,要注意的是 reversed() 比切片反转 [::-1] 要更快,因为前者只是生成了一个迭代器,而后者是创建了一个新的列表。如果是自己实现的话,代码如下:

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: # 等于right的也要考虑,因为只用了left一个指针遍历if s[left] != ' ': # 不是空白字符output.append(s[left])elif output[-1] != ' ': # 是第一个出现的空白字符output.append(s[left])left += 1return outputdef 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 - 1def reverse_each_word(self, l: list) -> None:n = len(l)start = end = 0while start < n:# 循环至单词的末尾while end < n and l[end] != ' ':end += 1# 翻转单词self.reverse(l, start, end - 1)# 更新start,去找下一个单词start = end + 1end += 1def 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)

分三步走:移除多余空格、将整个字符串反转、将每个单词反转。要注意各个指针的范围

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。