Python - 深夜数据结构与算法之 字符串常规操作

目录

一.引言

二.字符串简介

1.定义

2.遍历

3.比较

三.经典算法实战

1.To-Lower-Case [709]

?2.Len-Of-Last-Word [58]

3.Jewels-And-Stones [771]

4.Unique-Char [787]

5.String-To-Integer [8]

6.Longest-Common-Prefix [14]

7.Reverse-String [344]

8.Reverse-String-2 [541]

9.Reverse-Words-In-Str [151]

10.Reverse-String-In-Str 3[557]

11.Reverse-Only-Letters [917]

12.Group-Anagrams [49]

13.Valid-Palindrome [125]

14.Valid-Palindrome 2 [680]

15.Longest-Palindromic [5]

四.总结

---

一.引言

本文介绍字符串相关算法，以及字符串题目用到的一些关联数据结构。

二.字符串简介

1.定义

Python、Java 的 String 是不可变的，C++ 中是可变的。

2.遍历

3.比较

这里主要 Java 有区别，当使用 x==y 时，比较的是二者的指针，所以如果要比较字符串相等，需要使用 equals，如果忽略大小写则使用 IgnoreCase 的情况。

三.经典算法实战

1.To-Lower-Case [709]

转换小写:?https://leetcode.cn/problems/to-lower-case/description/

◆ 题目分析

最暴力的方法就是构造 {"A": "a", ... , "Z": "z"} 的映射，直接转换，最简单的方法是使用 .lower() 方法直接转换。这里我们熟悉一下 python 里字符串的写法，ord 可以获取其对应的?Unicode 码，而 chr 函数可以将整数?Unicode 码转换为 String。

◆ 字符串映射

class Solution(object):
    def toLowerCase(self, s):
        """
        :type s: str
        :rtype: str
        """
        re = []

        for char in s:
            if "A" <= char <= "Z":
                re.append(chr(ord(char) - ord("A") + ord("a")))
            else:
                re.append(char)

        # "".join([chr(ord(c) - ord('A') + ord('a')) if 'A' <= c <= 'Z' else c for c in s])
        return "".join(re)

这里基于一个等式即 ord("A") - ord("a") = ord("X") - ord("x")，移项即可。?

?2.Len-Of-Last-Word [58]

最后单词长度:?https://leetcode.cn/problems/length-of-last-word/description/

◆ 题目分析

本题用于熟悉字符串常用的方法:

- arr[::-1] 该操作用于反转字符串

- range(len(arr) - 1, -1, -1) 该操作用于从后向前遍历索引

- strip() 清除字符串头尾的空白符，空格、换行、制表符

- split() 使用空白符号对字符串进行分割

◆ 常规用法

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        #arr = s.split(" ")

        # 法1
        #for i in arr[::-1]:
        #    if len(i):
        #        return len(i)
        
        # 法2
        #for i in range(len(arr) - 1, -1, -1):
        #    if len(arr[i]):
        #        return len(arr[i])

        # 法3
        # return len(s.strip().split(" ")[-1])

        # 法4
        # return len(s.split()[-1])

        return 0

试了一下，方法 3 的速度最快。?

3.Jewels-And-Stones [771]

宝石与石头:?https://leetcode.cn/problems/jewels-and-stones/description/

◆ 题目分析

set 方法可以转换 list，也可以直接用 in 判断是否存在于 list，sum 可以统计 true 的个数。

◆ 常规用法?

class Solution(object):
    def numJewelsInStones(self, jewels, stones):
        """
        :type jewels: str
        :type stones: str
        :rtype: int
        """

        # 异常情况
        if len(jewels) * len(stones) == 0:
            return 0

        jewels = set(jewels)
        
        return sum(s in jewels for s in stones)

4.Unique-Char [787]

唯一字符:?https://leetcode.cn/problems/first-unique-character-in-a-string/description/

◆ 题目分析

使用 count = {} 记录每个字符的数量，如果 count = 1 则返回其索引，本题主要是空间辅助的思想。

◆ Map 计数?

class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """

        count = {}

        # 计数
        for char in s:
            if char not in count:
                count[char] = 0
            count[char] += 1

        for i in range(len(s)):
            if count[s[i]] == 1:
                return i
        
        return -1

◆ List 计数

class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """

        count = [0] * 26

        for i in range(len(s)):
            count[ord(s[i]) - ord("a")] += 1

        for i in range(len(s)):
            if count[ord(s[i]) - ord("a")] == 1:
                return i

        return -1

?通过 List 构建 26 个索引记数，该方法思想来源于记数排序。

5.String-To-Integer [8]

字符串换整数:?https://leetcode.cn/problems/string-to-integer-atoi/description/

◆ 题目分析

此题比较复杂，按照要求，面向示例一个一个改 bug，注意 int 不能越界是此题的一个点，经常会有题目要求检查越界的问题。

◆ 没有技巧都是泪

class Solution(object):
    def myAtoi(self, s):
        """
        :type s: str
        :rtype: int
        """

        # 去除前后空格
        s = s.strip()
        if len(s) == 0:
            return 0

        # 越界
        INT_MAX = 2 ** 31 - 1
        INT_MIN = -2 ** 31

        # 判断正负
        sign = 1

        if s[0] == "-":
            sign = -1
    
        if s[0] == "+" or s[0] == "-":
            s = s[1:]

        re = 0
        for char in s:
            if '0' <= char <= "9":
                re = re * 10 + int(char)
                # 上界
                if re > INT_MAX:
                    break
            else:
                break

        re = sign * re
        
        # 判断越界
        if re > INT_MAX:
            return INT_MAX
        if re < INT_MIN:
            return INT_MIN

        return re

6.Longest-Common-Prefix [14]

最长公共前缀:?https://leetcode.cn/problems/longest-common-prefix?

◆ 题目分析

每次判断当前索引字符，如果全部一致则遍历下一个索引，以此类推。

◆ 辅助空间

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """

        prefix = ""
    
        # 最长公共前缀取决于最短的字符
        n = min([len(s) for s in strs])
        char = ""

        for i in range(n):
            # 每一位一致才公共
            if len(set([s[i] for s in strs])) == 1:
                char += strs[0][i]
            else:
                break
        
        return char

◆ 无脑遍历

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """

        for i in range(len(strs[0])):
            for st in strs[1:]:
                if len(st) <= i:
                    return strs[0][:i]

                if st[i] != strs[0][i]:
                    return strs[0][:i]
        
        return strs[0]

7.Reverse-String [344]

反转字符串:?https://leetcode.cn/problems/reverse-string/

◆ 题目分析

构建起始双指针，从头到尾交换即可。

◆ 双指针

class Solution(object):
    def reverseString(self, s):
        """
        :type s: List[str]
        :rtype: None Do not return anything, modify s in-place instead.
        """
        st, end = 0, len(s) - 1

        while st < end:
            s[st], s[end] = s[end], s[st]
            st += 1
            end -= 1
    

8.Reverse-String-2 [541]

反转字符串2:?https://leetcode.cn/problems/reverse-string-ii/description/

◆ 题目分析

套用上方的 reverse 模版，这里主要理解题意，就是每 2k 步处理前 k 个，最后不够就都处理了。

走 K 步，for i in range(st, end, k) 这里是一个使用套路，类似上面从后往前走 range(st, -1 -1)。

◆ 模版套用?

class Solution(object):

    def reverse(self, s):
        """
        :type s: List[str]
        :rtype: None Do not return anything, modify s in-place instead.
        """
        st, end = 0, len(s) - 1

        while st < end:
            s[st], s[end] = s[end], s[st]
            st += 1
            end -= 1
        
        return s

    def reverseStr(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        t = list(s)
        for i in range(0, len(t), 2 * k):
            t[i: i+k] = self.reverse(t[i: i+k])
        return "".join(t)

9.Reverse-Words-In-Str [151]

反转字符串:?https://leetcode.cn/problems/reverse-words-in-a-string?

◆ 题目分析

还是反转字符串，只不过是部分反转，不是全部反转。

◆ 套用模版

class Solution(object):
    
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """

        s = s.strip()

        if len(s) == 0:
            return 0

        arr = [i for i in s.split(" ") if i != ""]

        st, end = 0, len(arr) - 1
        while st < end:
            arr[st], arr[end] = arr[end], arr[st]
            st += 1
            end -= 1

        return " ".join(arr)

10.Reverse-String-In-Str 3[557]

反转字符串3:?https://leetcode.cn/problems/reverse-words-in-a-string-iii/

class Solution(object):

    def reverse(self, s):
        start, end = 0, len(s) - 1

        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

        return "".join(s)

    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """

        arr = s.split(" ")

        return " ".join([self.reverse(list(text)) for text in arr])

11.Reverse-Only-Letters [917]

仅反转字母:?https://leetcode.cn/problems/reverse-only-letters/description/

class Solution(object):
    def isEng(self, char):
        return 'a' <= char <= 'z' or 'A' <= char <= 'Z'

    def reverseOnlyLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        start, end = 0, len(s) - 1
        s = list(s)

        while start < end:
            if not self.isEng(s[start]):
                start += 1
                continue
            if not self.isEng(s[end]):
                end -= 1
                continue

            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

        return "".join(s)

12.Group-Anagrams [49]

字母异位词分组:??https://leetcode.cn/problems/group-anagrams/description/

◆ 题目分析

本题主要掌握 sorted() 用法，其对字符串排序并返回一个排序后的字符列表。

◆ 套用模版

class Solution(object):

    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        re = {}

        for text in strs:
            sorted_text = ''.join(sorted(text))
            if sorted_text not in re:
                re[sorted_text] = []
            re[sorted_text].append(text)
        
        return re.values()

13.

所有异位词:?https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/

?◆ 暴力循环

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """

        p = ''.join(sorted(p))
        slen = len(p)

        return [i for i in range(len(s) - slen + 1) if ''.join(sorted(s[i: i+slen])) == p]

?◆ 滑动数组

class Solution(object):

    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        M, N, re = len(s), len(p), []

        if M < N:
            return re
        
        s_cnt = [0] * 26
        p_cnt = [0] * 26

        pivot = ord("a")

        for i in range(N):
            s_cnt[ord(s[i]) - pivot] += 1
            p_cnt[ord(p[i]) - pivot] += 1
        if s_cnt == p_cnt:
            re.append(0)
        
        for i in range(N, M):
            s_cnt[ord(s[i - N]) - pivot] -= 1
            s_cnt[ord(s[i]) - pivot] += 1

            if s_cnt == p_cnt:
                re.append(i - N + 1)
        
        return re

每次只滑动一个位置，只修改头尾的记数，如果两个数组相同则代表是异位词。

13.Valid-Palindrome [125]

验证回文串:?https://leetcode.cn/problems/valid-palindrome/description/

?◆ 题目分析

主要是判断是字符以及判断相等，也可以简单点直接 s = s[::-1]。

?◆ 双指针

class Solution(object):

    def isASC(self, c):
        return "a" <= c <= "z" or "A" <= c <= "Z" or "0" <= c <= "9"
        

    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """

        start, end = 0, len(s) - 1

        while start < end:
            if not self.isASC(s[start]):
                start += 1
                continue
            if not self.isASC(s[end]):
                end -= 1
                continue
            
            if s[start].lower() != s[end].lower():
                return False
            start += 1
            end -= 1
        
        return True

14.Valid-Palindrome 2 [680]

回文串2:?https://leetcode.cn/problems/valid-palindrome-ii/description/?

?◆ 题目分析

在不等于的情况下，删除左边或右边的节点，继续尝试。

?◆ 双指针

class Solution(object):

    def isValid(self, s, st, end):
        while st < end:
            if s[st] != s[end]:
                return False
            st += 1
            end -= 1
        return True


    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        start, end = 0, len(s) - 1

        while start < end:
            if s[start] == s[end]:
                start += 1
                end -= 1
            else:
                return self.isValid(s, start + 1, end) or self.isValid(s, start, end - 1)
        
        return True

15.Longest-Palindromic [5]

最长回文子串:?https://leetcode.cn/problems/longest-palindromic-substring/description/

?◆ 题目分析

回文串可以是 bab 即奇数的情况，也可以是 baab 的双数情况，对于每一个位置 i，我们判断 i 为中心的回文串和 i,i+1 为中心的回文串哪个长，更新 res 最终返回。

?◆ 双指针

class Solution(object):

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        # 中心扩散
        def palindrome(s, st, end):
            while st >= 0 and end < len(s) and s[st] == s[end]:
                end += 1
                st -= 1
            return s[st + 1: end]

        res = ""

        for i in range(len(s)):
            sub1 = palindrome(s, i, i) # 以 i 为中心扩散
            sub2 = palindrome(s, i, i+1) # 以 i,i 为中心扩散

            res = sub1 if len(sub1) > len(res) else res
            res = sub2 if len(sub2) > len(res) else res
        
        return res

                

四.总结

关于字符串基本操作的题目就写到这里，现在已经是? 23:42 了，又是快乐做题的一晚。上面的题目大都是 Easy & Middle，可以看到字符串基本操作的主要思想一种是使用双指针在原址遍历，这样比较节省内存空间，另外就是借助辅助空间，类似 set、list、dict 构造 count 从而辅助计算。