第三章_字符串_2019-03-18 第三章_字符串_2019-03-18

字符串的特点

重要
广泛性
1、可以将字符串转化为字符数组
2、很多题貌似不是字符串类型，但是可以转化为字符串类型题解决

常见概念回文、子串、子序列（不连续）、前缀树（Trie树）、后缀树和后缀数组、匹配、字典序
常见操作 【第三章_字符串_2019-03-18】增、删、改、差、字符替换、字符串旋转
常见类型题

规则判断
1、判断字符串是否符合整数规则
2、判断字符串是否符合浮点数规则
3、判断字符串是否符合回文字符串规则
数字运算
int、long表达的整数范围有限，所以，用字符串实现大整数，我们需要模拟与大整数相关的四则运算
与数组操作有关的题目
将字符串转化为字符数组解决的问题
字符计数
1、解决方法：hash表
2、固定长度的数组：因为hash是将数据映射到任意整数表示的索引的位置，在C/C++中整数的范围是0255（256个数），Java中的整数范围是065535（65536个数），所以用固定长度的数组模拟hash表时， C/C++中需要数组长度为256，Java中需要的数组长度为65536.
3、例如：滑动窗口问题、寻找无重复子串问题、计算变位词问题
动态规划
1、最长公共子串问题
2、字长公共子序列问题
3、最长回文子串问题
4、最长回文子序列问题
搜索类型
给定str1、str2，需要将str1变换到str2，要求str1每次只能变化一个位置，要求打印变化轨迹
高级算法与数据结构解决的问题
1、Manacher（马拉车）算法求回文子串问题
2、KMP算法解决匹配问题
3、通过构造高级数据结构解决问题，如：前缀树结构、后缀树和后缀树结构（面试或笔试中一般不会出现，因为太复杂，不好表达）

经典题

表面是二叉树问题，实际是字符串问题，如：给定二叉树A和二叉树B，问树A中是否有与树B拓扑结构相同的子树。
1、一般方法：即二叉树的遍历，时间复杂度为O(N * M)
2、优化方法：将A、B序列化为字符串，通过解决匹配问题来解决该问题，时间复杂度为O(N + M)
给定字符串A、B，判断A、B是否互为变形词（从集合的角度考察时A、B是一样的）
用hash表解决，可以考虑用固定长度的数组模拟hash表
给定字符串str，已知字符串有足够的缓冲可以容纳替换完的字符串，将其中所有的空格替换为‘%20’。
先计算替换后的字符串的长度，然后从str的最后一个位置开始遍历str，依次从后往前填充替换后的字符串存储空间，当遇到空格时填入‘%20’。（时间复杂度为O(n)，空间复杂度为O(1)）
给定一个字符串，其中只包含左括号和右括号两种字符，亲判断该字符串是不是一个整体有效的括号组合。
用变量number来记录当前右括号和左括号的差值，如果遇到左括号，number+1，如果遇到右括号，number-1，如果出现number<0，返回false，如果直到最后，number ~=0，则返回false，其他情况返回true。（时间复杂度为O(n)，空间复杂度为O(1)）
给定str，求最长无重复子串
1、需要用到一个hash表和一个prior变量
2、hash：存储之前遍历到的每个字符出现的向左最远位置，prior：存储遍历上一个字符时求得的向左最长无重复子串的最远位置。
3、当遍历位置i时，从hash表中取出它最近上一次出现的位置，记录为位置A
4、prior指向的位置记录为B
5、比较A和B，它们靠右的那个位置即为当前字符向左最长无重复子串的最远位置。
6、更新hash表和prior，继续前面操作，直到str被遍历完。