算法长征（4）字符串

字符串

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

class Solution:
    def replaceSpace(self, s: str) -> str:
        return s.replace(" ", "%20")

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

• 字符串切片、列表遍历拼接、字符串遍历拼接

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        return s[n:] + s[:n]
		def reverseLeftWords(self, s: str, n: int) -> str:
      	# 列表遍历拼接
        res = []
        for i in range(n, len(s)):
            res.append(s[i])
        for i in range(n):
            res.append(s[i])
        return ''.join(res)
    def reverseLeftWords(self, s: str, n: int) -> str:
      	# 字符串遍历拼接
        res = "" # 字符为不可变对象，每轮都新建
        for i in range(n, len(s)):
            res += s[i]
        for i in range(n):
            res += s[i]
        return res

以 Python 为例开展三种方法的效率测试：

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        m, n = len(s1), len(s2)
        if m > n:
            return False
        key = [0] * 26
        cur = [0] * 26 
        for i in range(m):
            key[ord(s1[i]) - ord('a')] += 1
            cur[ord(s2[i]) - ord('a')] += 1
        if key == cur:
            return True
        for j in range(n - m):
            cur[ord(s2[j]) - ord('a')] -= 1
            cur[ord(s2[j + m]) - ord('a')] += 1
            if key == cur:
                return True
        return False

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

• 字典数组、滑动窗口

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len, p_len = len(s), len(p)
        if s_len < p_len:
            return []
        ans = []
        s_count = [0] * 26
        p_count = [0] * 26
        for i in range(p_len):
            s_count[ord(s[i]) - 97] += 1
            p_count[ord(p[i]) - 97] += 1
        if s_count == p_count:
            ans.append(0)
        for i in range(s_len - p_len):
            s_count[ord(s[i]) - 97] -= 1
            s_count[ord(s[i + p_len]) - 97] += 1
            if s_count == p_count:
                ans.append(i + 1)
        return ans

给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

• 滑动窗口

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left, lookup, n = 0, set(), len(s)
        max_len, cur_len = 0, 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left]) # 移除做元素直到无重复，到最小无重复子串
                left += 1
                cur_len -= 1
            if cur_len > max_len:
                max_len = cur_len
            lookup.add(s[i])
        return max_len

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

• 滑动窗口

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        s_len, t_len = len(s), len(t)
        if s_len < t_len:
            return ""
        # 0 不删除
        sdict, tdict = defaultdict(int), Counter(t)
        left, conut = 0, 0
        res = ""
        for i in range(s_len):
            sdict[s[i]] += 1
            if sdict[s[i]] <= tdict[s[i]]:
                conut += 1
            while left <= i and sdict[s[left]] > tdict[s[left]]:
                # 加一个A就减一个A...(无用后缀)
                sdict[s[left]] -= 1
                left += 1
            if conut == t_len:
                if not res or (i - left + 1 < len(res)):
                    res = s[left:i + 1]
        return res

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

class Solution:
    def isPalindrome(self, s: str) -> bool:
        n = len(s)
        left, right = 0, n - 1
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if left < right:
                if s[left].lower() != s[right].lower():
                    return False
                left, right = left + 1, right - 1
        return True

给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

class Solution:
    def validPalindrome(self, s: str) -> bool:
        # 回溯， 广度优先 【字符串长度，暴搜必定超时】
        def checkPalind(l, r):
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True
        n = len(s)
        left, right = 0, n - 1
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return checkPalind(left + 1, right) or checkPalind(left, right - 1)
        return True

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

• 动态规划、双指针+中心扩展、==Manacher算法==

class Solution:
    def countSubstrings(self, s: str) -> int:
        # 双指针+中心扩散
        result = 0
        def _extend(s, i, j, n):
            res = 0
            while i >= 0 and j < n and s[i] == s[j]: # 确定中心点
                i -= 1
                j += 1
                res += 1 # 扩散过程也是答案
            return res
        for i in range(len(s)):
            result += _extend(s, i, i, len(s)) #以i为中心
            result += _extend(s, i, i+1, len(s)) #以i和i+1为中心
        return result

    def countSubstrings(self, s: str) -> int:
        # 动态规划 dp[i][j]: s[i:j] 是否为回文子串
        # dp[i+1][j-1] -> dp[i][j] 遍历顺序 
        n = len(s)
        dp = [[False] * (n) for _ in range(n)]
        ans = 0
        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if s[i] == s[j]:
                    if j - i <= 1:
                        ans += 1
                        dp[i][j] = True
                    elif dp[i+1][j-1]:
                        ans += 1
                        dp[i][j] = True
        return ans