###常见概念
1.回文
2.子串（连续）
3.子序列（不连续）
4.前缀树（Trie树）
5.后缀数和后缀数组
6.匹配
7.字典序
####下面是一些字符串常见的算法题：
> 1.对于两棵彼此独立的二叉树A和B，请编写一个高效算法，检查A中是否存在一棵子树与B树的拓扑结构完全相同。
给定两棵二叉树的头结点A和B，请返回一个bool值，代表A中是否存在一棵同构于B的子树。
思路1：先将树转化为字符串，然后通过kmp算法匹配，最差O(n+k)，如果暴力匹配（O(n*k)）
~~~
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class IdenticalTree {
public boolean chkIdentical(TreeNode t1, TreeNode t2) {
String t1Str = serialByPre(t1);
String t2Str = serialByPre(t2);
return KmpSearch(t1Str, t2Str) != -1;
}
public String serialByPre(TreeNode head) {
if (head == null) {
return "#!";
}
String res = head.val + "!";
res += serialByPre(head.left);
res += serialByPre(head.right);
return res;
}
// KMP匹配
public int KmpSearch(String ss, String pp)
{
char[] s=ss.toCharArray();
char[] p=pp.toCharArray();
int[] next=getNext(p);
int i = 0;
int j = 0;
int sLen = s.length;
int pLen = p.length;
while (i < sLen && j < pLen)
{
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
//获取next数组
public int[] getNext(char[] p)
{
int pLen = p.length;
int[] next=new int[pLen];
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k])
{
++k;
++j;
next[j] = k;
}
else
{
k = next[k];
}
}
return next;
}
}
~~~
>2.对于两个字符串A和B，如果A和B中出现的字符种类相同且每种字符出现的次数相同，则A和B互为变形词，请设计一个高效算法，检查两给定串是否互为变形词。
给定两个字符串A和B及他们的长度，请返回一个bool值，代表他们是否互为变形词。
测试样例：
"abc",3,"bca",3
返回：true
思路1：hash表统计一下
~~~
import java.util.*;
public class Transform {
public boolean chkTransform(String A, int lena, String B, int lenb) {
if(A==null||B==null||A.length()!=B.length())
return false;
int[] h=new int[256];
for(int i=0;i<A.length();++i){
h[(int)A.charAt(i)]++;
}
for(int i=0;i<B.length();++i){
if(h[(int)B.charAt(i)]--==0)
return false;
}
return true;
}
}
~~~
>3.对于一个字符串，请设计一个算法，只在字符串的单词间做逆序调整，也就是说，字符串由一些由空格分隔的部分组成，你需要将这些部分逆序。
给定一个原字符串A和他的长度，请返回逆序后的字符串。
测试样例：
"dog loves pig",13
返回："pig loves dog"
思路：翻转局部，再翻转整体
~~~
import java.util.*;
public class Reverse {
public String reverseSentence(String A, int n) {
// write code here
if(A==null)
return A;
String[] ss=A.split(" ");
StringBuilder sb=new StringBuilder();
for(int i=0;i<ss.length;++i){
sb.append(reverse(ss[i]));
sb.append(" ");
}
return reverse(sb.toString().trim());
}
public String reverse(String s){
char[] ss=s.toCharArray();
for(int i=0;i<ss.length/2;++i){
char t=ss[i];
ss[i]=ss[ss.length-1-i];
ss[ss.length-1-i]=t;
}
return String.valueOf(ss);
}
}
~~~
>4.对于一个字符串，请设计一个算法，将字符串的长度为len的前缀平移到字符串的最后。限制条件，空间复杂度O(1)
给定一个字符串A和它的长度，同时给定len，请返回平移后的字符串。
测试样例：
"ABCDE",5,3
返回："DEABC"
思路：翻转，再翻转
~~~
import java.util.*;
public class Translation {
public String stringTranslation(String A, int n, int len) {
// write code here
if(A==null)
return A;
len=len%A.length();
char[] a=A.toCharArray();
reverse(a,0,len-1);
reverse(a,len,a.length-1);
reverse(a,0,a.length-1);
return String.valueOf(a);
}
public void reverse(char[] a,int s,int e){
while(s<=e){
char t=a[s];
a[s]=a[e];
a[e]=t;
s++;
e--;
}
}
}
~~~
>5.对于一个给定的字符串数组，请找到一种拼接顺序，使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的。
给定一个字符串数组strs，同时给定它的大小，请返回拼接成的串。
测试样例：
["abc","de"],2
"abcde"
思路：比较两个字符串组合起来的大小
~~~
import java.util.*;
public class Prior {
class MyComparator implements Comparator<String> {
@Override
public int compare(String a, String b) {
return (a + b).compareTo(b + a);
}
}
public String findSmallest(String[] strs, int n) {
// write code here
if(strs.length<1)
return null;
Arrays.sort(strs,new MyComparator());
StringBuilder sb=new StringBuilder();
for(int i=0;i<strs.length;++i){
sb.append(strs[i]);
}
return String.valueOf(sb);
}
}
~~~
>6.对于一个字符串，请设计一个算法，判断其是否为一个合法的括号串。
给定一个字符串A和它的长度n，请返回一个bool值代表它是否为一个合法的括号串。
测试样例：
"(()())",6
返回：true
测试样例：
"()a()()",7
返回：false
测试样例：
"()(()()",7
返回：false
~~~
import java.util.*;
public class Parenthesis {
public boolean chkParenthesis(String A, int n) {
// write code here
if(A.length()<1)
return false;
int num=0;
for(int i=0;i<A.length();++i){
if(A.charAt(i)=='('){
num++;
}else if(A.charAt(i)==')'){
num--;
}
if(num<0)
return false;
}
if(num!=0)
return false;
return true;
}
}
~~~
>7.对于一个字符串,请设计一个高效算法，找到字符串的最长无重复字符的子串长度。
给定一个字符串A及它的长度n，请返回它的最长无重复字符子串长度。保证A中字符全部为小写英文字符，且长度小于等于500。
测试样例：
"aabcb",5
返回：3
思路：hash表map保存当前字符的上一次出现的位置，pre保存当前位置的上一个位置i-1的字符上次出现的位置（通过位置求出长度）
~~~
import java.util.*;
public class DistinctSubstring {
public int longestSubstring(String A, int n) {
// write code here
if(A.length()<1||n<1)
return 0;
char[] a=A.toCharArray();
int[] map=new int[256];
for(int i=0;i<map.length;++i)
map[i]=-1;
int pre=-1;
int len=0;
int cur=0;
for(int i=0;i<n;++i){
pre=Math.max(pre,map[a[i]]);
cur=i-pre;
len=Math.max(len,cur);
map[a[i]]=i;
}
return len;
}
}
~~~
