一、字符串基础知识
字符串概念
- 略
二、字符串知识扩展
字符串中的双指针
- 略
字符串题目 | 双指针
题目一：字符串中的变位词
输入字符串s1和s2，如何判断字符串s2中是否包含字符串s1的某个变位词？如果字符串s2中包含字符串s1的某个变位词，则字符串s1至少有一个变位词是字符串s2的子字符串。假设两个字符串中只包含英文小写字母。例如，字符串s1为"ac"，字符串s2为"dgcaf"，由于字符串s2中包含字符串s1的变位词"ca"，因此输出为true。如果字符串s1为"ab"，字符串s2为"dgcaf"，则输出为false。
题目分析
难度： ⭐⭐
思路： 题目读懂是关键，首先什么是变位词，变位词指的是组成词的元素及其个数均不变，仅仅是顺序不一样。而题意可简述为字符串s1的变位词在字符串s2中是否存在。暴力求解过程：将s2倒序转换为s3，从s1字符串中遍历获取变位词s4，如果s4属于s3子串，那么满足条件。（暴力求解时间复杂度过高，效率难以提升）标记次数：每组变位词中字母出现次数一定一致，可以通过计算字母次数。s1属于每个字母记为1，s2记为-1，在字符串移动过程中，移出的字符串计数+1，移入的-1，如果标记数组全为0则表示满足条件。
参考代码
Tips：2023-10-24 00:09
题目二：字符串中的所有变位词
输入字符串s1和s2，如何找出字符串s2的所有变位词在字符串s1中的起始下标？假设两个字符串中只包含英文小写字母。例如，字符串s1为"cbadabacg"，字符串s2为"abc"，字符串s2的两个变位词"cba"和"bac"是字符串s1中的子字符串，输出它们在字符串s1中的起始下标0和5。
题目分析
难度： ⭐⭐
思路： 同题目一（字符串中的变位词）类似，此时只需要新增一个数组用于存放每个符合条件的子字符串开始的下标即可。
参考代码
Tips：2023-11-14 09:59
题目三：不含重复字符的最长子字符串
输入一个字符串，求该字符串中不含重复字符的最长子字符串的长度。例如，输入字符串"babcca"，其最长的不含重复字符的子字符串是"abc"，长度为3。
题目分析
难度： ⭐
思路： 求最大的不重复字符串，可以利用双指针伸缩滑块的思想解决。使用一个Map或者Set记录字符是否包含在左右指针区间内，在遍历字符串字符的过程中，右指针右移动，如果不包含在内，记录到Map或Set中，右指针继续右移动。如果包含在内，左指针字母在Map或Set进行移除，左指针右移，直到右指针字母在Map或Set找不到位置，随后继续移动右指针，直到末尾。整个过程中使用一个变量记录长度，最后返回即可。
参考代码
Tips：2023-11-14 10:01
题目四：包含所有字符的最短字符串
输入两个字符串s和t，请找出字符串s中包含字符串t的所有字符的最短子字符串。例如，输入的字符串s为"ADDBANCAD"，字符串t为"ABC"，则字符串s中包含字符'A'、'B'和'C'的最短子字符串是"BANC"。如果不存在符合条件的子字符串，则返回空字符串""。如果存在多个符合条件的子字符串，则返回任意一个。
题目分析
难度： ⭐⭐
思路： 同双指针的思想，可以通过Map记录t字符串钟字符串所出现的次数；随后遍历s字符串，定义左右指针，指向s子字符串的首尾，如果子字符串未完全包好t字符串，右移右指针；如果已经包含，右移左指针；直到左指移动到最右侧，可以优化为右指针到最右侧，在包含t字符串的情况下左指针至无法移动；在整个过程中记录最小字符串长度（如果优化判断子字符串是否完全包含t字符串是比较困难的一点）。
参考代码
Tips：2023-11-14 10:03
字符串题目 | 回文字符串
题目一：有效的回文
给定一个字符串，请判断它是不是回文。假设只需要考虑字母和数字字符，并忽略大小写。例如，"Was it a cat Isaw？"是一个回文字符串，而"race a car"不是回文字符串。
题目分析
难度： ⭐
思路： 可以采用左右双指针向中间靠拢的方式，来逐一比较左右字符是否一致（注意跳过空格），不区分大小写可统一转换为小写比较；也可以先对字符串转为小写再做处理。
参考代码
Tips：2023-11-14 10:04
题目二：最多删除一个字符得到回文
给定一个字符串，请判断如果最多从字符串中删除一个字符能不能得到一个回文字符串。例如，如果输入字符串"abca"，由于删除字符'b'或'c'就能得到一个回文字符串，因此输出为true。
题目分析
难度： ⭐
思路： 回文数判断依旧可以按照双指针的模式去寻找，题目询问是否能删除一个字符得到回文字符串，那么可以在遍历的过程中，遇到左右不等的字符时，直接判断[left+1,right]或[left,right-1]的字符串是不是回文数即可（即舍弃left指针字符或者right指针字符，使用调删除的字符名额）。
参考代码
Tips：2023-11-14 10:06
题目三：回文子字符串的个数
给定一个字符串，请问该字符串中有多少个回文连续子字符串？例如，字符串"abc"有3个回文子字符串，分别为"a"、"b"和"c"；而字符串"aaa"有6个回文子字符串，分别为"a"、"a"、"a"、"aa"、"aa"和"aaa"。
题目分析
难度： ⭐⭐
思路： 在前几题中都使用了从两端往里滑动指针的方式寻找，本题可换一个角度，从里往外滑动寻找回文串。即以某个点startIndex为起点向着左右两边同时移动指针，如果是回文串计数并继续，如果不是则结束当前移动。由于回文串可能是基数也可能是偶数长度，所以应将以startIndex或[startIndex, startIndex + 1]作为起点子串所寻找出的结果加起来。最开始的起点startIndex从下标0开始，直到最后下标到达字符串末尾结束。
参考代码
Tips：2023-11-14 10:08
三、章节小结
变位词和回文是很有意思的文字游戏，在与字符串相关的算法面试题中，它们出现的频率很高。如果两个字符串包含的字符及每个字符出现的次数都相同，只是字符出现的顺序不同，那么它们就是一组变位词。通常可以用一个哈希表来统计每个字符出现的次数，有了哈希表就很容易判断两个字符串是不是一组变位词。
回文是一类特殊的字符串。不管是从前往后还是从后往前读取其每一个字符，得到的内容都是一样的。通常可以用两个指针来判断一个字符串是不是回文，要么两个指针从字符串的两端开始向中间移动，要么两个指针从中间开始向两端移动。