在Java中，字符串是指由一连串字符组成的序列。字符串是final类，不可变，很适合作为Map中的键。string 在做字符串改变等操作时，实际上是先建一个stringbuffer,改变字符串以后再赋值给string。效率上string builder>string buffer>string，string包含太多对中间过程和临时变量，需要垃圾回收，影响效率。同时Java中也提供了stringtokener这样的字符串处理类。
注意：String a = “a”+”b”+”c”,在方法区只创建了一个对象。
（1）除去字符串中的空格
算法思路：先遍历原字符串，求得空格个数和字符串长度。计算替换后字符串长度。从后往前一次赋值。
（2）KMP算法-字符串匹配
算法思路：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，继续逐个比较后续字符。当一趟匹配过程中出现字符比较不等时，不回溯i指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。时间效率达到T(n) =O(n+m)
部分匹配和next 数组
next数字0和1下标的数据分别时0和1 ，其他的为，当某个字符前的字符串的前缀和后缀一致的数量是n,那么这个字符对应的next数组中的位置数据为n+1;
使用nextval 数组可以加速运算。
”A”,当它不匹配时，按照next行回溯到标号1也为字母A，这时再匹配A是徒劳的，因为已知A不匹配，所以就继续退回到标号1字母A的next(1)=0。为了直接点进行优化，就有了nextval行:
j=5，P(5)=A，next(5)=1，P(1)=A=P(5)，所以nextval(5)=next(1)=0;
j=6，P(6)=B，next(6)=2，P(2)=B=P(6)，所以nextval(6)=next(2)=1;
j=7，P(7)=D，next(7)=3，P(3)=C!=P(7)，所以nextval(7)=next(7)=3;
代码见：https://github.com/yuanfuqiang456/LeetCode/blob/master/src/String/KMP.java
(3)strcpy
字符串复制算法，常见于腾讯面试中：
char * strcpy(char *dst,const char*src)
{
if((dst==NULL)||(src==NULL))
return NULL;
char *ret = dst; //[1]
while ((*dst++=*src++)!='\0'); //[2]
return ret;//[3]
}
注意：const 修饰：源字符串参数用const修饰，防止修改源字符串；
空指针检查：源指针和目的指针都有可能会出现空指针的情况，所以应该对其进行检查；
为什么要设置ret 指针以及返回ret指针的位置[3]，由于目的指针dst已经在进行移动了，所以用辅助指针ret表明首指针；
以上所示[2]处，为简单的字符串的复制过程，正好表明strcpy函数遇到'\0'将会停止；
（4）strncpy
strncpy的功能和strcpy相似，只是它复制时多了一个终止条件。即是未遇到原串的'\0’，如果已经复制了n个字符（n为提供的参数长度），复制同样会终止。
char* strncpy(char* dest, const char*src, int len)
{
assert(dest!=NULL &&src!=NULL);
char* temp=dest;
int i=0;
while(i++ < len && (*temp++ = *src++)!='\0') ;
if(*(temp)!='\0')
*temp='\0';
return dest;
}
(5)memcpy
strncpy只能复制字符串，但memcpy对类型没有要求;strncpy有两个终止条件，memcpy只有一个终止条件，那就是复制n个字节。（n是memcpy的第三个参数）;要特别注意目的地址和源地址重合的问题，拷贝前要加以判断。实现这个函数时一般要把原来的指针类型转换成char*，这样每次移动都是一个字节。
void* mymemcpy(void* dest, void* src,int len)
{
int i=0;
char* tempdest=(char*)dest;
char* tempsrc=(char*)src;
if(tempdest(tempsrc+len-1))
{
while(i
{
*tempdest++ =*tempsrc++;
i++;
}
}
else
{
tempdest+=len;
tempsrc+=len;
i=len;
while(i>0)
{
*tempdest--= *tempsrc--;
i--;
}
}
return dest;
}
(6)字符串翻转
例如how are you ----you are how
算法思路：首先整个字符串转一遍，其次，每个单词再转一遍
代码见：https://github.com/yuanfuqiang456/LeetCode/blob/master/src/String/ReverseString.java
(7)字符串包含
给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断字符串B中所有字母是否都在字符串A里？
算法思路：方法一：逐个字符比较；方法二：先排序A,B中字符，再逐个扫描；方法三：每个字符用一个素数代替，如果可以整除则包含；方法四：hash表。
(8)判断一个字符串是否是回文
算法思路：从两边往中间逼近或者从中间往两边转。
代码见：https://github.com/yuanfuqiang456/LeetCode/blob/master/src/String/HuiWen.java
(9)最长回文子串
又叫对称子字符串的最大长度，输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
算法思路：
方法一：Manacher算法。
首先通过在每个字符的两边都插入一个特殊的符号，将所有可能的奇数或偶数长度的回文子串都转换成了奇数长度。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。
此外，为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如$#a#b#a#。
以字符串12212321为例，插入#和$这两个特殊符号，变成了 S[] = "$#1#2#2#1#2#3#2#1#"，然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左或向右扩张的长度（包括S[i]）。
比如S和P的对应关系：
S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
可以看出，P[i]-1正好是原字符串中最长回文串的总长度，为5。
方法二：字符串A翻转为B，求A和B最长公共字串的长度
（10）第一个只出现一次的字符
在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。按出现顺序赋值1，2，3，4。方法一：计数排序。辅助数组中出现次数为1 的第一个。找到对应的字符。方法二：使用LinkedhashMap。
（11）在字符串中删除特定的字符
输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。
例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”。
算法思路：先找到待删除内容，用# 标记。求出除#之外的字符串长度。倒序复制。
（12）字符个数的统计
char *str = "AbcABca"; 写出一个函数，查找出每个字符的个数，区分大小写，要求时间复杂度是n
算法思路：使用哈希表，遍历一遍原字符串即可
（13）最小子串
给一篇文章，里面是由一个个单词组成，单词中间空格隔开，再给一个字符串指针数组，比如char*str[]={"hello","world","good"};
求文章中包含这个字符串指针数组的最小子串。注意，只要包含即可，没有顺序要求。
算法思路：文章也可以理解为一个大的字符串数组，单词之前只有空格，没有标点符号。设置两个范围，当前范围和最小范围。交替更新起始位置和终止位置。
（14）最长重复子串
一个长度为10000的字符串，写一个算法，找出最长的重复子串，如abczzacbca,结果是bc。
算法思路：从每个字符开始，分别求其后缀，放入hashmap，key为对应后缀，value为出现次数中，需要两次循环遍历；
（15）字符串的压缩
算法思路：一个字符串，压缩其中的连续空格为1个后，对其中的每个字串逆序打印出来。比如"abc
efg hij"打印为"cba gfe jih"。
（16）字符串的移动
字符串为+号和26个字母的任意组合，把+号都移动到最左侧，把字母移到最右侧并保持相对顺序不变，要求时间和空间复杂度最小。
算法思路：字符串翻转
（17）字符串求MOD
有N个数，组成的字符串，如012345，求出字串和取MOD3==0的子串，如012 12 123 45。
算法思路：利用前缀数组和后缀数组，并将字符串转为数字。
（18）括号匹配算法
可以利用队列，队列前后分别为（）则可以出（，而）也不必放入，最后看队列中是否还有（或者）。
（19）改变字符串中一组括号的位置，使其括号匹配。
依次调整，并利用括号匹配算法。
代码见：https://github.com/yuanfuqiang456/LeetCode/blob/master/src/String/KuoHao.java
网友评论