算法学习第七天----字符串

字符串

验证回文字符串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例：

输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

输入: "race a car"
输出: false
解释："raceacar" 不是回文串

提示：

1 <= s.length <= 2 * 105

字符串 s 由 ASCII 字符组成

思路：回文字符串的定义是从头读和从尾读是一样的，所以设置两个指针分别从前往后和从后往前，只要所有字符都一样就是回文字符串。此题需要实现处理字符串中的标点符号和所有字符都改成大写或者小写。

class Solution:
    def isPalindrome(self, s: str) -> bool:
        res = []
        for i in s:
            if i.isalnum():
                res.append(i.lower())
        head, end = 0, len(res) - 1
        while head <= end:
            if res[head] != res[end]:
                return False
            else:
                head += 1
                end -= 1
        return True

翻转字符串里的单词

给你一个字符串 s ，逐个翻转字符串中的所有单词。单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

示例：

输入：s = "the sky is blue"
输出："blue is sky the"

输入：s = "  hello world  "
输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。

输入：s = "  Bob    Loves  Alice   "
输出："Alice Loves Bob"

输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"

提示：

1 <= s.length <= 104

s 包含英文大小写字母、数字和空格 ' '

s 中 至少存在一个 单词

思路：理解题意之后，大致就是要以单词为整体反转句子，那就好办了，以空格分隔倒叙join。很多时候感觉题目很难，可能是没有理解题意。加油~

class Solution:
    def reverseWords(self, s: str) -> str:
        s_list = s.split(' ')
        res = []
        for i in s_list:
            if i != '':
                res.append(i)
        return ' '.join(res[::-1])

验证回文字符串 Ⅱ

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例：

输入: s = "aba"
输出: true

输入: s = "abca"
输出: true
解释: 你可以删除c字符。

输入: s = "abc"
输出: false

提示：

1 <= s.length <= 105

s 由小写英文字母组成

思路：此题与上题类似，如果不需要删除字符就是回文字符串，那自然是好的。如果要删字符，删哪个？肯定是删不相等的时候，那这个时候删哪个，那就两个都试试呗~既然只是删一个字符，所以也用不上递归。

class Solution:
    def validPalindrome(self, s):
        def check(low, high):
            i, j = low, high
            while i < j:
                if s[i] != s[j]:
                    return False
                else:
                    i += 1
                    j -= 1
            return True
        
        head, end = 0, len(s)-1
        while head < end:
            if s[head] == s[end]:
                head += 1
                end -= 1
            else:
                return check(head +1, end) or check(head, end-1)
        return True

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a或 2[4] 的输入。

示例：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "3[a2[c]]"
输出："accaccacc"

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

思路：

遍历字符串

如果当前字符是数字，num += s[i]，知道s[i+1]!=数字，然后num进栈
如果当前字符是右括号，则开始弹出待计算字符，直到当前字符为左括号停止，接着弹出左括号
合并栈

代码如下：

class Solution:
    def decodeString(self, s: str) -> str:
        NUM = '0123456789'
        stack , num, str_= [], '', ''
        for i in range(len(s)):
            if s[i] in NUM:
                num += s[i]
                # 当下一位不是数字的时候，类型转换
                if s[i+1] not in NUM:
                    stack.append(int(num))
                    num = ''
            # 右括号开始计算
            elif s[i] == ']':
                str_ = ''
                # 需要将待计算的字符出栈
                while stack[-1] != '[':
                    str_ = stack.pop() + str_
                # 弹出左括号
                stack.pop()
                # 将计算结束的字符穿入栈
                stack.append(str_ * stack.pop())
            else:
                stack.append(s[i])
        return ''.join(stack)

算法学习第七天----字符串