1. 1. 字符串
a. 反转字符串
i. 栈
ii. 时间复杂度n，空间复杂度n
b. 字符串的全排列(类似数组部分集合的子集)
i. 构造队列，字符串首字符入队
ii. 对字符串按位置进行遍历
iii. for循环内部记下此时队列的size，循环size次，每次对于出队的元素，循环在特定位置插入当前字符后入队
iv. 时间复杂度n!
c. 最小编辑代价
d. KMP算法
i. 构造next函数，动态规划思路
1. 1. a[0]=-1
2. 2. a[1]=0;
3. 3. for循环从2号位置开始， 如果i-1号位置的next值为-1，那么a[i]=0
4. 4. 如果next[i-1]不等于-1，那么说明n-1位的最长前缀后下一位是next[j-1]，那么判断arr[j-1]是否与arr[next[j-1]]是否相等，如果相等next[j]=k+1
5. 5. 构造while循环，进行模式识别，
a. 如果当前位置相同，i++;j++; 如果此时j=模式串的长度，匹配成功
b. 如果当前位置不同，next[j]==-1, j=0;i++;
c. 如果当前位置不同,next【j】!=-1， j=next[j],继续比较
e. 最长重复子串abcabc
i. 滑动窗口为长度的一半
ii. 双层循环，外层窗口--，内层起始位置—
iii. 通过charAt判断是否相等
f. 字符串转换成ip地址
i. 递归，ip地址分四部分
ii. 获取第一部分合法的情况下，判断剩余部分是不是可以分成3个合法的块儿
1. 1. 第一部分1个字符，2个字符，3个字符的情况
2. 2. 当多个字符时，首字符不为0
3. 3. 用当前第一块儿和后面递归结果进行合并，最后返回
iii. 当剩余部分为1时，判断是否为合法数字，<256且首字符不为0，添加到ret
iv. 时间复杂度n^2
g. 将字符串转换为整数
h. 大数乘法
i. 构造乘法，str1n 构造进位C,从后往前，留意c
ii. 构造加法，从后往前，留意c
iii. 注意符号，注意乘数的位数对应补0
iv. 时间复杂度nm, 空间复杂度m+n
i. 验证IP地址
i. 分v4,v6两种规则验证
ii. 注意v4中大小的判断，split后的字符串高位不能是0
iii. Split(“[.]”)
iv. 时间复杂度n
j. 字符串数组的最长公共前缀
i. 拿第一个字符串作为参照物，遍历循环查找
ii. 两层循环，如果有一个为false就返回
iii. 时间复杂度为n字符串的最短长度
k. 正则表达式匹配
l. 判断回文
i. 如果是奇数，从n/2 +1，n/2 +1开始判断是否回文
ii. 如果是偶数，从n/2，n/2 +1判断是否回文，分别往两边--，++
iii. 时间复杂度n
m. 最小覆盖子串
n. 字符串变形，字母大小写取反，空格分开的取反
i. 注意char<’A’,类似的用法简单好用
ii. 不确定空格数量时，不要用空格split,容易出问题
iii. 从头开始遍历字符串，找到完整的单词后，大小写取反，放到结果字符串的开头
iv. 如果当前是空格，直接放到结果字符串的开头
v. 时间复杂度n
o. 通配符匹配
p. 判断是否是旋转字符串，比如nihao,haoni这一对就是旋转字符串
i. 同时遍历两个字符串，一个从前开始，一个从后开始
ii. 如果当两个字符串相等，判断剩余部分是否相等，如果相等则返回true
iii. 时间复杂度n
q. 判断括号序列的合法性
i. 用栈
ii. 时间复杂度n, 空间复杂度n
r. 大数加法
i. 从尾部开始加，设计进位c
ii. 最后别拉下c
iii. 时间复杂度max(m+n),空间复杂度m+n
