字符串常和其他数据类型放一起考

数组

字符串下标天然是数组

栈

后进先出，包括括号匹配、路径拆分等字符串题目，注意，python中的栈用list的append和pop实现栈的压入弹出。

哈希表

主要是用来做快速匹配

队列

先进先出

字符串方法

• 获取字符串长度: len(str)
• 判断字符串是否相等: str== str2
• 获取字符串的子串: str[begin: end:step​]
• 拆分字符串: str.split(regex,maxsplit)
• 获取下标: python 只有index()
• 大小写转换: lower() upper()
• 返回指定下标的字符：str[i]

 

剑指 Offer II 014. 字符串中的变位词

题目描述

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

剑指 Offer II 014. 字符串中的变位词 - 力扣（LeetCode） (leetcode-cn.com)

题解

滑动固定大小的窗口，双指针

用字符统计就可以做，遍历一次s2

def checkInclusion(self, s1: str, s2: str) -> bool:
    arr1, arr2, lg = [0] * 26, [0] * 26, len(s1)
    if lg > len(s2):
        return False
    # 维护一个arr2, 使它在s2上往右滑直到碰到尾巴
    for i in range(lg):
        arr1[ord(s1[i]) - ord('a')] += 1
        arr2[ord(s2[i]) - ord('a')] += 1

    for j in range(lg, len(s2)):
        if arr1 == arr2:
            return True
        arr2[ord(s2[j - lg]) - ord('a')] -= 1
        arr2[ord(s2[j]) - ord('a')] += 1
    return arr1 == arr2

剑指 Offer II 015. 字符串中的所有变位词

题目描述

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

变位词 指字母相同，但排列不同的字符串

剑指 Offer II 015. 字符串中的所有变位词 - 力扣（LeetCode） (leetcode-cn.com)

题解

固定窗口双指针

上一道题改一下：

def findAnagrams(self, s: str, p: str) -> List[int]:
    arr1, arr2, lg = [0] * 26, [0] * 26, len(p)
    ret = []
    if lg > len(s):
        return []
    # 维护一个arr2, 使它在s2上往右滑直到碰到尾巴
    for i in range(lg):
        arr1[ord(p[i]) - ord('a')] += 1
        arr2[ord(s[i]) - ord('a')] += 1

    for j in range(lg, len(s)+1):
        if arr1 == arr2:
            ret.append(j-lg)
        if j<len(s):
            arr2[ord(s[j - lg]) - ord('a')] -= 1
            arr2[ord(s[j]) - ord('a')] += 1
    return ret

剑指 Offer II 016. 不含重复字符的最长子字符串

题目描述

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

剑指 Offer II 016. 不含重复字符的最长子字符串 - 力扣（LeetCode） (leetcode-cn.com)

题解

双指针+hash表

双指针，维护一个字典，key为字符，value为上一次遇到该字符的位置

def lengthOfLongestSubstring(self, s: str) -> int:
    # 双指针+hash表
    dic, res, i = {}, 0, -1
    for j in range(len(s)):
        if s[j] in dic:
            i = max(dic[s[j]], i) # 更新左指针 i
        dic[s[j]] = j # 哈希表记录
        res = max(res, j - i) # 更新结果
    return res

动态规划dp

动态规划列表 dp ，dp[j] 即 代表以字符 s[j] 为结尾的 “最长不重复子字符串” 的长度。所以只需要一次for循环

def lengthOfLongestSubstring(self, s: str) -> int:
        #动态规划+hash表 设动态规划列表 dp ，dp[j]    即 代表以字符 s[j] 为结尾的 “最长不重复子字符串” 的长度。但是由于只要max, 只需用一个变量做动态规划额外的空间
        dic = {} #记录s[i] 的 i  s[i] 为距离s[j]最近的那个字符  即s[i]=s[j] i<j
        
        tmp = 0
        res = 0
        for j in range(len(s)):
            i = dic.get(s[j],-1) #获取索引i  参数-1表示找不到就返回-1
            dic[s[j]] = j
            if tmp < j-i:  #tmp中存的是dp[j-1]  即当前（shangyige）字符的dp[值]
                tmp = tmp+1
            else:
                tmp = j-i
            res = max(res,tmp)  # max(dp[j-1],dp[j])
        return res