Grind75第6天 | 5.最长回文子串、76.最小覆盖子串、438.找到字符串中所有字母异位词

发布时间:2024年01月11日

5.最长回文子串

题目链接:https://leetcode.com/problems/longest-palindromic-substring

解法:

这个题用中心扩散法,思路不容易想到,具体实现也不容易,需要多理解几次。

对字符串进行遍历,在 i 这个位置,首先往左寻找与当期位置相同的字符,直到遇到不相等为止。
然后往右寻找与当前位置相同的字符,直到遇到不相等为止。
最后左右双向扩散,直到左和右不相等。这时候就得到了以 i 这个位置进行扩散能得到的最长回文子串。

但是,这个并不一定是全局的最长回文子串。继续从 i+1 这个位置按以上的步骤向两边进行扩散,同时最大长度也重置为1。

遍历结束后,得到了最长回文子串的左坐标和长度,就可以得到最长回文子串了。

参考题解:中心扩散法

边界条件:无

时间复杂度:O(n^2)

空间复杂度:O(1)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s

        max_left = 0
        max_len = 0
        length = 0
        for mid in range(len(s)):
            left = mid - 1
            right = mid + 1

            # 往左寻找与当期位置相同的字符,直到遇到不相等为止
            while left >= 0 and s[left] == s[mid]:
                left -= 1
                length += 1

            # 往右寻找与当期位置相同的字符,直到遇到不相等为止
            while right < len(s) and s[right] == s[mid]:
                right += 1
                length += 1

            # 往两边寻找
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
                length += 2

            # 更新从当前位置扩散的最长回文串
            if length > max_len:
                max_len = length
                max_left = left

            # 重置为1,以便从下一个位置开始扩散
            length = 1

        return s[max_left+1: ][:max_len]

76.最小覆盖子串

题目链接:https://leetcode.com/problems/minimum-window-substring

解法:

这道题参考了labuladong的题解,思路如下:

参考题解:滑动窗口

边界条件:无

时间复杂度:O(n+m),n和m分别为s和t的长度

空间复杂度:O(c),c为字符集的大小,即2*26

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        target = {}
        for c in t:
            target[c] = target.get(c, 0) + 1

        window = {}
        left, right = 0, 0
        # 记录最小覆盖子串的起始位置和长度
        start = 0
        min_len = float('inf')
        # 记录覆盖目标子串中字符的个数(同时满足个数要求)
        valid = 0
        while right < len(s):
            # 移入窗口的字符
            c = s[right]
            right += 1
            if c in target:
                window[c] = window.get(c, 0) + 1
                # 字符和个数相等,则加1
                if window[c] == target[c]:
                    valid += 1

            # 对左侧窗口收缩
            while valid == len(target):
                # 更新最小覆盖子串
                if (right - left) < min_len:
                    start = left
                    min_len = right - left

                c = s[left]
                left += 1
                if c in target:
                    if window[c] == target[c]:
                        valid -= 1
                    # 注意这是在valid减1后
                    window[c] -= 1

        if min_len == float('inf'):
            return ''
        return s[start:][:min_len]

438.找到字符串中所有字母异位词

题目链接:https://leetcode.com/problems/find-all-anagrams-in-a-string

解法:

这个题和76.最小覆盖子串的思路差不多,都是用滑动窗口,都参考了labuladong的题解。

这个题可以在76.最小覆盖子串的代码基础上稍加修改得到:

  • 把异位词的左下标不断加入到结果集中
  • 判断左侧窗口收缩的条件是窗口的长度等于目标字符串的长度。

边界条件:无

时间复杂度:O(n+m),n和m分别为s和t的长度

空间复杂度:O(c),c为字符集的大小,即26

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        target = {}
        for c in p:
            target[c] = target.get(c, 0) + 1
        
        window = {}
        left, right = 0, 0
        res = []
        valid = 0
        while right < len(s):
            c = s[right]
            right += 1
            # 向右移动,把字符加入窗口
            if c in target:
                window[c] = window.get(c, 0) + 1
                if window[c] == target[c]:
                    valid += 1
                
            # 当窗口长度和目标字符串长度一样时,添加到结果集,并收缩左侧窗口
            while right - left >= len(p):
                if valid == len(target):
                    res.append(left)

                c = s[left]
                left += 1
                if c in target:
                    # 原本满足,但现在左侧收缩了就不满足了
                    if window[c] == target[c]:
                        valid -= 1
                    window[c] -= 1

        return res
文章来源:https://blog.csdn.net/Jack199274/article/details/135518819
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。