###常見概念
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;
}
}
~~~
