施坤的博客
0%

字符串的算法总结

发表于 更新于 分类于 阅读次数： Valine：

验证回文串

  • 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
  • 说明：本题中，我们将空字符串定义为有效的回文串。
  • 本题来自这里

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isPalindrome(self, s: str) -> bool:
    	# 字符串转为小写
        new_str = s.lower()
        new_list = list()
        for i in new_str:
         # 过滤数字
            if i.isalnum():
                new_list.append(i)
        # 字符串转换为list，顺序和逆序进行对比
        return (new_list[::1] == new_list[::-1])

反转字符串

  • 给定一个字符串数组，将其反转

代码

  • 第一种：使用字符串切片
1
2
3
s = 'aaacccsss'
result = s[::-1]
print(result)
  • 第二种：使用列表的reverse方法
1
2
3
4
s = 'aaacccsss'
l = list(s)
l.reverse()
result = "".join(l)
  • 第三种：使用栈
1
2
3
4
5
6
7
8
def func(s):
    l = list(s) #模拟全部入栈
    result = ""
    while len(l)>0:
        result += l.pop() #模拟出栈
    return result
result = func(s)

反转字符串中的单词 III

  • 给定一个字符串 s，将字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
  • 题目来自这里

示例1:

输入: “the sky is blue”
输出: “blue is sky the”

示例2:

输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例3:

输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解题思路

因为 Python 的字符串是不可变的，所以在原字符串空间上进行切换顺序操作肯定是不可行的了。但我们可以利用切片方法。

  • 将字符串按空格进行分割，分割成一个个的单词。
  • 再将每个单词进行反转。
  • 然后再将每个单词连接起来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(s.strip().split()[::-1])
        # return " ".join([t for t in s.strip().split()][::-1])

    def reverseWords1(self, s: str) -> str:
       # 将字符串按空格进行分割，分割成一个个的单词列表,去掉了首位两端的空格
        s1 = s.strip().split()
        # 反转单单词列表
        s2 = s1[::-1]
        # 单词列表转换为字符连接起来
        s3 = " ".join(s2)
        return s3


resp = Solution().reverseWords("the sky is blue")
print(resp)