微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

LeetCode Cookbook 字符串习题下篇

开始字符串部分了,这一部分的花的时间不少了今天上午给整理出来,主要就是一些有关字符串的基本函数应用,非常需要勤加练习.

632. 最小区间 ** (最小堆)

题目链接：632. 最小区间
题目大意：你有 k 个非递减排列的整数列表。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

例如：

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释： 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

解题思路：超级难,最小堆可以很大程度减小计算量,但函数不好记! 不过这代码太有魅力,需要好好学习学习!

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        rangeL,rangeR = -10**9,10**9
        maxValue = max(vec[0] for vec in nums)
        priorityQueue = [(vec[0],i,0) for i,vec in enumerate(nums)]
        heapq.heapify(priorityQueue)
        # print(priorityQueue,maxValue)
        # print('__________________')

        while True:
            minValue,row,idx = heapq.heappop(priorityQueue)
            if maxValue - minValue < rangeR - rangeL:
                rangeL,rangeR = minValue,maxValue
            if idx == len(nums[row])-1:
                break
            maxValue = max(maxValue,nums[row][idx+1])
            heapq.heappush(priorityQueue,(nums[row][idx+1],row,idx+1))
        #     print(priorityQueue,minValue,maxValue)
        #     print('-----------------------')
        # print(priorityQueue,rangeL,rangeR)
        return [rangeL,rangeR]

748. 最短补全词

题目链接：748. 最短补全词
题目大意：给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出 words 中的最短补全词。补全词是一个包含 licensePlate 中所有字母的单词。忽略 licensePlate 中的数字和空格。不区分大小写。如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。

例如：licensePlate = “aBc 12c”，那么它的补全词应当包含字母 ‘a’、‘b’ （忽略大写）和两个 ‘c’ 。可能的补全词有 “abccdef”、“caaacab” 以及 “cbca” 。请返回 words 中的最短补全词。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words 中第一个出现的那个。

例如:

输入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
输出："steps"
解释：最短补全词应该包括 "s"、"p"、"s"（忽略大小写） 以及 "t"。
"step" 包含 "t"、"p"，但只包含一个 "s"，所以它不符合条件。
"steps" 包含 "t"、"p" 和两个 "s"。
"stripe" 缺一个 "s"。
"stepple" 缺一个 "s"。
因此，"steps" 是唯一一个包含所有字母的单词，也是本例的答案。

解题思路：题目不难细节拉满需要按字符长度进行排序 words.sort(key = lambda i:len(i))

class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
        hash_map = [ch.lower() for ch in licensePlate if ch.isalpha()]
        counter = collections.Counter(hash_map)
        words.sort(key = lambda i:len(i))
        print(words)
        for word in words:
            tmp = collections.Counter(word)
            if all(tmp[ch] >= counter[ch] for ch in counter):
                return word
        return '-1'

771. 宝石与石头

题目链接：771. 宝石与石头
题目大意：给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。字母区分大小写，因此 “a” 和 “A” 是不同类型的石头。

例如：

输入：jewels = "aA", stones = "aAAbbbb"
输出：3

解题思路：两种方法计数是关键!

(一) 方法一

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        ans = 0
        jewels = set(jewels)
        for ch in stones:
            if ch in jewels:
                ans += 1
        return ans

(二) 方法二

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewelsSet = set(jewels)
        return sum(s in jewelsSet for s in stones)

819. 最常见的单词 **

题目链接：819. 最常见的单词
题目大意：定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词。题目保证至少有一个词不在禁用列表中，而且答案唯一。禁用列表中的单词用小写字母表示，不含标点符号。段落中的单词不区分大小写。答案都是小写字母。

例如：

输入: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
输出: "ball"
解释: 
"hit" 出现了3次，但它是一个禁用的单词。
"ball" 出现了2次 (同时没有其他单词出现2次)，所以它是段落里出现次数最多的，且不在禁用列表中的单词。 
注意，所有这些单词在段落里不区分大小写，标点符号需要忽略（即使是紧挨着单词也忽略， 比如 "ball,"）， 
"hit"不是最终的答案，虽然它出现次数更多，但它在禁用单词列表中。

解题思路：正则表达这部分内容需要好好汇总一下这一直是一个让我头疼的地方.
补充正则的一些常用函数:

 		>>>import re
        >>> re.split('\W+', 'runoob, runoob, runoob.')
        ['runoob', 'runoob', 'runoob', '']
        >>> re.split('(\W+)', ' runoob, runoob, runoob.') 
        ['', ' ', 'runoob', ', ', 'runoob', ', ', 'runoob', '.', '']
        >>> re.split('\W+', ' runoob, runoob, runoob.', 1) 
        ['', 'runoob, runoob, runoob.']

(一)方法一

import re

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
    
        # 无敌的正则
        return Counter(w for w in re.findall(r'\w+',paragraph.lower()) \
         if w not in set(banned)).most_common(1)[0][0]

(二)方法二

import re

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        s = re.split('\W+',paragraph)
        counter = collections.Counter([ch.lower() for ch in s if ch.isalpha() ])
        # print(counter)
        for word in counter.most_common():
            if word[0] not in banned:
                return word[0]

28. 统计子串中的唯一字符 **

题目链接：28. 统计子串中的唯一字符
题目大意：我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。例如：s = “LEETCODE” ，则其中 “L”, “T”,“C”,“O”,“D” 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为 32 位整数。

注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。

例如：

输入: s = "ABC"
输出: 10
解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
     其中，每一个子串都由独特字符构成。
     所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10

解题思路：简单题,重拳出击,两种编写方法,思路是一致的.

'''
示例:"ABA"
中间过程显示: 
arr= [-1, 0, 2, 3]
ans= 4
arr= [-1, 1, 3]
ans= 8

示例:"ABC"
中间过程显示: 
arr= [-1, 0, 3]
ans= 3
arr= [-1, 1, 3]
ans= 7
arr= [-1, 2, 3]
ans= 10
'''

class Solution:
    def uniqueLetterString(self, s: str) -> int:
        hash_map = collections.defaultdict(list)
        for i,ch in enumerate(s):
            hash_map[ch].append(i)
        
        ans = 0
        for arr in hash_map.values():
            arr = [-1]+arr+[len(s)]
            print('arr=',arr)
            for i in range(1,len(arr)-1):
                ans += (arr[i]-arr[i-1])*(arr[i+1]-arr[i])
            print('ans=',ans)
        return ans

880. 索引处的解码字符串

题目链接：880. 索引处的解码字符串
题目大意：给定一个编码字符串 S。请你找出解码字符串并将其写入磁带。解码时，从编码字符串中每次读取一个字符，并采取以下步骤：

如果所读的字符是字母，则将该字母写在磁带上。
如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。
现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。

例如：

输入：S = "leet2code3", K = 10
输出："o"
解释：解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。字符串中的第 10 个字母是 "o"。

解题思路：倒序绝了!

class Solution:
    def decodeAtIndex(self, s: str, k: int) -> str:
        # 解码后的字符串长度
        size = 0
        for c in s:
            if c.isdigit():
                size *= int(c)
            else:
                size += 1
        
        for c in reversed(s):
            k %= size
            if k == 0 and c.isalpha():
                return c
            
            if c.isdigit():
                size /= int(c)
            else:
                size -= 1

925. 长按键入

题目链接：925. 长按键入
题目大意：你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。

例如：

输入：name = "alex", typed = "aaleex"
输出：true
解释：'alex' 中的 'a' 和 'e' 被长按。

解题思路：抓住关键点那就是计数相同的字母个数的较量!

class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        m,n = len(name),len(typed)
        i=j=0
        if name[0] != typed[0] or name[-1] != typed[-1]: return False
        while i<m and j<n:
            cnt1,cnt2 = 0,0
            while i<m-1 and name[i] == name[i+1]: 
                cnt1 += 1
                i += 1
            while j<n-1 and typed[j] == typed[j+1]: 
                cnt2 += 1
                j += 1
            if cnt2 >= cnt1: 
                i += 1
                j += 1
            else:
                return False
        return i==m and j == n

942. 增减字符串匹配

题目链接：942. 增减字符串匹配
题目大意：由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:

如果 perm[i] < perm[i + 1] ，那么 s[i] == ‘I’
如果 perm[i] > perm[i + 1] ，那么 s[i] == ‘D’
给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中任何一个。

例如：

输入：s = "IDID"
输出：[0,4,1,3,2]

解题思路：简单题双指针

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        lo = 0
        hi = n = len(s)
        perm = [0] * (n+1)
        for i,ch in enumerate(s):
            if ch == 'I':
                perm[i] = lo
                lo += 1
            else:
                perm[i] = hi
                hi -= 1
        # 最后加一个数
        perm[n] = lo
        return perm

984. 不含 AAA 或 BBB 的字符串 **

题目链接：984. 不含 AAA 或 BBB 的字符串
题目大意：给定两个整数 a 和 b ，返回任意字符串 s ，要求满足：

s 的长度为 a + b，且正好包含a 个 ‘a’ 字母与 b 个 ‘b’ 字母；
子串 ‘aaa’ 没有出现在 s 中；
子串 ‘bbb’ 没有出现在 s 中。

例如：

输入：a = 1, b = 2
输出："abb"
解释："abb", "bab" 和 "bba" 都是正确答案。

输入：a = 4, b = 1
输出："aabaa"

解题思路：这道题需要贪心做法但总有一种动态规划的意思在其中! 需要好好看看.

class Solution(object):
    def strWithout3a3b(self, A, B):
        ans = []

        while A or B:
            
            # 判断 写 A or B
            # 1. 两个相同的时候 判断是否为B 如果是 写A
            # 1. 如果 A>B 写 A
            if len(ans) >= 2 and ans[-1] == ans[-2]:
                writeA = ans[-1] == 'b'
            else:
                writeA = A >= B

            if writeA:
                A -= 1
                ans.append('a')
            else:
                B -= 1
                ans.append('b')
            

        return "".join(ans)

1078. Bigram 分词

题目链接：1078. Bigram 分词
题目大意：给出第一个词 first 和第二个词 second，考虑在某些文本 text 中可能以 “first second third” 形式出现的情况，其中 second 紧随 first 出现，third 紧随 second 出现。对于每种这样的情况，将第三个词 “third” 添加到答案中，并返回答案。

例如：

输入：text = "alice is a good girl she is a good student", first = "a", second = "good"
输出：["girl","student"]

解题思路： Counter 特别好用.

from itertools import permutations

class Solution:
    def findOcurrences(self, text: str, first: str, second: str) -> List[str]:
        ans = []
        s = text.split()
        n = len(s)
        return [s[i+2] for i in range(n-2) if s[i] == first and s[i+1] == second]

1108. IP 地址无效化

题目链接：1108. IP 地址无效化
题目大意：给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。所谓无效化 IP 地址，其实就是用 “[.]” 代替了每个 “.”。

例如：

输入：address = "1.1.1.1"
输出："1[.]1[.]1[.]1"

解题思路： replace 没啥好说的

class Solution:
    def defangIPaddr(self, address: str) -> str:
        return address.replace('.','[.]')

1189. “气球” 的最大数量

题目链接：1189. “气球” 的最大数量
题目大意：给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 “balloon”（气球）。字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 “balloon”。

例如：

输入：text = "nlaebolko"
输出：1

解题思路：计数题

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        counter = collections.Counter(text)
        ans = 0
        return min(min([counter[ch] for ch in 'ban']),min([counter[ch]//2 for ch in 'lo']))

1221. 分割平衡字符串

题目链接：1221. 分割平衡字符串
题目大意：在一个平衡字符串中，‘L’ 和 ‘R’ 字符的数量是相同的。给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
返回可以通过分割得到的平衡字符串的最大数量。

例如：

输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

解题思路：双指针 + 计数

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        ans = 0
        n = len(s)
        cnt1,cnt2 = 0,0
        for ch in s:
            if ch == 'L': cnt1 += 1
            if ch == 'R': cnt2 += 1
            if cnt1 == cnt2: 
                ans += 1
                cnt1,cnt2 = 0,0
        return ans

1234. 替换子串得到平衡字符串 **

题目链接：1234. 替换子串得到平衡字符串
题目大意：有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符，且长度为 n 的字符串。假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。你可以用和「待替换子串」长度相同的任何其他字符串来完成替换。请返回待替换子串的最小可能长度。如果原字符串自身就是一个平衡字符串，则返回 0。

例如：

输入：s = "QQWE"
输出：1
解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。

解题思路：费劲题目需要动态规划来思考不过这里就不搞那些了,弄个简单些的代码思路,专门针对这道题.

class Solution:
    def balancedString(self, s: str) -> int:
        counter = collections.Counter(s)
        n,k = len(s),len(s)//4
        L,R,ans = 0,-1,len(s)
        while L<n:
            if counter['Q']>k or counter['W']>k or counter['E']>k or counter['R']>k:
                if R+1<n:
                    R += 1
                    counter[s[R]] -= 1
                else:
                    break
            else:
                ans = min(ans,R-L+1)
                counter[s[L]] += 1
                L += 1
        return ans

1455. 检查单词是否为句中其他单词的前缀

题目链接：1455. 检查单词是否为句中其他单词的前缀
题目大意：给你一个字符串 sentence 作为句子并指定检索词为 searchWord ，其中句子由若干用单个空格分隔的单词组成。请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。如果 searchWord 是某一个单词的前缀，则返回句子 sentence 中该单词所对应的下标（下标从 1 开始）。如果 searchWord 是多个单词的前缀，则返回匹配的第一个单词的下标（最小下标）。如果 searchWord 不是任何单词的前缀，则返回 -1 。字符串 s 的前缀是 s 的任何前导连续子字符串。

例如：

输入：sentence = "i love eating burger", searchWord = "burg"
输出：4
解释："burg" 是 "burger" 的前缀，而 "burger" 是句子中第 4 个单词。

解题思路：正常做就成,此题不难!

class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        s = sentence.split()
        n = len(searchWord)
        for i,word in enumerate(s):
            if len(word)>=n and word[:n]==searchWord:
                return i+1
        return -1

76. 最小覆盖子串

题目链接：76. 最小覆盖子串
题目大意：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

例如：

输入：s = "Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

解题思路：脑壳疼, 动态规划双指针做移动浮标.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict
        findout = defaultdict(int)
        for i in t:
            findout[i] += 1
        min_len, res = float('inf'), ""
        l, counter = len(s), len(t)
        left = right = 0
        #------------------------------
        while right < l:
            if findout[s[right]] > 0:
                counter -= 1
            findout[s[right]] -= 1
            right += 1
            while counter == 0:
                if min_len > right - left:
                    min_len = right - left
                    res = s[left:right]
                if findout[s[left]] == 0:
                    counter += 1
                findout[s[left]] += 1
                left += 1 
        #-------------------------------------
        return res

总结

字符串这一部分算整完了,当然这些题还是比较少的,这周开始开始参加积分竞赛了,希望能及格!

本文含有隐藏内容，请开通VIP 后查看

LeetCode Cookbook 字符串习题下篇

LeetCode Cookbook 字符串习题下篇

632. 最小区间 ** (最小堆)

748. 最短补全词

771. 宝石与石头

819. 最常见的单词 **

28. 统计子串中的唯一字符 **

880. 索引处的解码字符串

925. 长按键入

942. 增减字符串匹配

984. 不含 AAA 或 BBB 的字符串 **

1078. Bigram 分词

1108. IP 地址无效化

1189. “气球” 的最大数量

1221. 分割平衡字符串

1234. 替换子串得到平衡字符串 **

1455. 检查单词是否为句中其他单词的前缀

76. 最小覆盖子串

总结

网站公告

今日签到

热门文章

最新发布

LeetCode Cookbook 字符串习题 下篇

LeetCode Cookbook 字符串习题 下篇

632. 最小区间 ** (最小堆)

748. 最短补全词

771. 宝石与石头

819. 最常见的单词 **

28. 统计子串中的唯一字符 **

880. 索引处的解码字符串

925. 长按键入

942. 增减字符串匹配

984. 不含 AAA 或 BBB 的字符串 **

1078. Bigram 分词

1108. IP 地址无效化

1189. “气球” 的最大数量

1221. 分割平衡字符串

1234. 替换子串得到平衡字符串 **

1455. 检查单词是否为句中其他单词的前缀

76. 最小覆盖子串

总结

网站公告

今日签到

热门文章

最新发布

LeetCode Cookbook 字符串习题下篇

LeetCode Cookbook 字符串习题下篇