[数据结构与算法]题目特点梳理_字符串

概念

1. 回文
2. 子串（连续）
3. 子序列（不连续）
4. 前缀树（Trie树）
5. 后缀树和后缀数组
6. 匹配
7. 字典序

操作

1. 数组：增删查改
2. 字符的替换
3. 字符串的旋转

常见类型

规则判断

①判断字符串是否符合整数规则
②判断字符串是否符合浮点数规则
③判断字符串是否符合回文字符串规则

数字运算

int和long类型表达整数范围有限所以经常用字符串实现大整数与大整数相关的加减乘除操作,需要模拟笔算的过程

与数组有关

①数组有关的调整、排序等操作需要掌握
②快速排序的划分过程需要掌握和改写

字符计数

①哈希表
②固定长度的数组
C/C++ (256长度),JAVA (65536长度)
③滑动窗口问题、寻找无重复字符子串问题，计算变位词问题

动态规划

最长公共子串
最长公共子序列
最长回文子串
最长回文子序列

搜索

高级算法与数据结构解决的问题

①Manacher算法解决最长回文子串问题
②KMP算法解决字符串匹配问题
③前缀树结构
④后缀树和后缀数组