文字列関連アルゴリズムの整理
本文は個人の学習過程に基づいて、いくつかの常用知識を蓄積する.後続の参考学習に供する.文字列に関するアルゴリズムは、面接やプロジェクトでよく使われています.そこで、ここで記録を整理します.文字列は文字タイプの配列と見なすことができるので、配列ソート、配列検索、順序調整に関するアルゴリズムと組み合わせることができます.さらに、文字列の比較とサブ文字列の操作は、1つのツリーが別のツリーのサブツリーと一致するかどうかなどの他の問題を解決するために使用できます.文字列操作には、回文の概念、文字マッチングの問題、ディクショナリ順序の問題、サブシーケンスの問題、サブストリングの問題、接頭辞ツリー、接尾辞ツリー、接尾辞配列の概念など、多くの基本的な知識点が含まれます.また,動的計画の問題は,最長共通サブストリング,最長共通サブストリング,最長エコーサブストリング,最長エコーサブストリングなどである.KMPアルゴリズム、接頭辞ツリー、接尾辞ツリー、および接尾辞配列
注意:赤いエリアこの記事では詳しく説明していませんが、後でブログを書きます.
一、文字列に関するタイトルディレクトリ
1*、AツリーのサブツリートポロジーがBツリートポロジーと同じかどうか
2、文字列AとBの中で、文字の種類と各文字の出現回数が同じかどうか
3、文字列回転語の問題
4*、文の逆順序の問題
5、文字列の左右シフト問題
6*、最小ディクショナリシーケンス文字をつづる問題
7、スペースの置換問題
8**、最長重複なし文字列問題
二、具体的なテーマの詳細
1、AツリーのサブツリートポロジーがBツリートポロジーと同じかどうか説明:2本の互いに独立したツリーAとBについて、Aに1本のサブツリーがBツリーのトポロジーと完全に同じであるかどうかを確認する.2本の二叉木のヘッドノードAとBを指定し、AにBと同じサブツリーが存在するかどうかを表すbool値を返します.分析:一般的な方法は、Aの各株の木を巡って、Bの木のトポロジー構造と同じかどうかを判断することであり、この方法の時間的複雑度はO(m*n)である.もう1つの優れた解決策は、Aの前順遍歴文字列にBの前順遍歴文字列が含まれているか否かを判断することである.ツリーの問題を文字列の問題に変換し,KMPアルゴリズムで時間複雑度をO(m+n)に下げる.サンプルコード:
まとめ:ツリーのサブツリーと別のツリーのトポロジーマッチング問題,文字列に変換されたサブストリング問題,古典的なKMPアルゴリズムを用い,時間複雑度O(m+n),空間複雑度O(logn)であった.KMPアルゴリズムはよく使われるアルゴリズムで、KMPアルゴリズムを学ぶ必要があります.
2、文字列AとBのうち、文字の種類と各文字の出現回数が同じかどうかの説明:2つの文字列AとBの場合、AとBの中で出現する文字の種類が同じで、各文字の出現回数が同じであれば、AとBは互いに変形語である.2つの与えられた列が互いに変形語であるかどうかを確認するアルゴリズムを作成してください.2つの文字列AとBとその長さを指定し、互いに変形語であるかどうかを表すbool値を返します.解析:この問題は、補助配列を使用して解決できます.長さ256の整数配列helpを宣言し、文字列Aを1回巡回すると、配列Aの各文字の出現回数を統計し、help配列に記録することができる.次に、文字列Bを巡回し、各文字がhelpの位置に対応する値を1減算し、配列内の値が0未満の場合、AとBは変形語ではなく、そうでない場合、AとBは互いに回転語であることを示す.例コード:要約なし:アシスト配列を使用して問題を解決することは、よく使用される方法です.補助配列は問題を簡略化し,問題の複雑さを低減できる.通常の問題を解決する場合は、配列のほかに、ハッシュテーブル、キュー、スタックなどを補助ツールとして使用して問題を解決します.
3、文字列回転語の問題説明:一つの文字列Aに対して、Aの前の任意の部分を後ろに移動して形成された文字列をAの回転語と呼ぶ.例えばA=「12345」、Aの回転語は「12345」、「23451」、「34512」、「45123」、「51234」である.2つの文字列AとBについて、AとBが互いに回転語であるか否かを判断してください.2つの文字列AとBとその長さlena,lenbを指定し、互いに回転語であるかどうかを表すbool値を返します.解析:Aの文字長をnとします.回転語の構造的特徴により、2つのAを加算して1つの2 n長の文字列Cを得ることができ、C下付き[0...n-1]の任意の位置から長さnの文字列Diを後方に切り取ると、DiはAの回転語である.そして得られたすべてのDi集合には,Aのすべての回転語が含まれている.では,問題をBがCのサブストリングであるかどうかの問題に変換することができる.同様に、KMPアルゴリズムが使用されます.サンプルコード:要約なし:なし
4、文の逆順序問題の説明:文字列について、文字列の単語間で逆順序調整を行うアルゴリズムを設計してください.つまり、文字列はスペースで区切られた部分から構成されており、これらの部分を逆順序にする必要があります.元の文字列Aとその長さを指定し、逆の文字列を返します.テストサンプル:“dog loves pig”、13は結果を返します:“pig loves dog”分析:問題を解く構想は、まず文全体を逆順して、それから各単語を逆順します.各単語を逆順にしてから、文全体を逆順にすることもできます.時間的複雑度はO(n),空間的複雑度はO(1)であった.サンプルコード:
まとめ:コードのハイライト部分は、反転するたびに左右の境界を統計するテクニックで、従来のプログラミングで境界を決定するという悩みを解決することができます.
5、文字列の左右シフト問題
説明:文字列の場合、lenの文字列の長さの接頭辞を文字列の最後に平行移動するアルゴリズムを設計します.文字列Aとその長さを指定し、lenを指定すると、平行移動後の文字列を返します.
テストサンプル:
"ABCDE",5,3
結果を返します:DEABC
分析:この問題は前の問題と同じ問題に属し、すべて回転問題である.問題を解くには、まず左右の各部分を回転させ、それから全体を回転させることを考えます.
サンプルコード:なし
まとめ:なし
6、最小ディクショナリシーケンス文字をつづる問題の説明:指定された文字列の配列について、すべての小文字列をつづる大文字列がすべての可能なつづりの中でディクショナリシーケンスが最小になるように、つづり順序を見つけてください.文字列配列strsを指定し、サイズを指定して、つなぎ合わせた列を返します.テストサンプル:["abc","de"],2は結果を返します:“abcde”分析:1つの誤区を解決します---よくこのような問題を解決して1つの誤区に陥ることができて、例えば2つの文字列“b”と“ba”に入って、“b”は“ba”より小さくて、“b”は“ba”の前の“bba”に置くべきで、しかし、正しい順序は“bab”です.この問題を見直し,文字列AとBの前後順を判断する際には,A+BとB+Aの大きさを比較してAとBの前後順を決定すべきである.サンプルコード:
まとめ:カスタムソートルールを学習します.
7、スペースの置換問題
説明:文字列のスペースをすべて「%20」に置き換える方法を作成します.新しい文字を格納するのに十分なスペースがあり、文字列の真の長さ(1000以下)を知っていると仮定し、文字列が大文字と小文字の英字で構成されることを保証します.string iniStringが元の列であり、列の長さint lenが与えられ、置換されたstringが返される.
試験例:「Mr John Smith」,13
結果を返します:“Mr%20 John%20 Smith”
解析:文字列内のスペースの個数nzeroを最初に取得し、len+2*nzeroの長さの戻り文字配列retを作成します.IniStringの末尾から前への遍歴を開始し、retの末尾に文字を順次入力し、スペースに遭遇した場合、retに%20を挿入します.IniStringを巡回すると、要求に合致する文字列が得られます.
サンプルコード:なし
まとめ:なし
8、最長重複なし文字列問題
説明:文字列の場合、効率的なアルゴリズムを設計し、文字列の最長重複文字のないサブ列の長さを見つけます.文字列Aとその長さnを指定し、その最長の重複しない文字列のサブ列の長さを返します.Aの文字がすべて小文字の英字で、長さが500以下であることを保証します.
試験例:「aabcb」,5
結果を返します:3
解析:変数preと補助配列mapを設定し、preは前の重複文字のないサブ列の開始位置を記録し、mapは文字の出現位置を記録します.preとmapを決定すると、現在の位置文字の最後の重複文字のないサブ列の長さが得られる.
サンプルコード:
まとめ:文字列内のi位置文字で終わる、重複文字のないサブ列の長さを決定します.preとmap[arr[i]]の2つの値の大きい値に基づいて重複文字列のない左境界を決定し,iを右境界として完成した.
注意:赤いエリアこの記事では詳しく説明していませんが、後でブログを書きます.
一、文字列に関するタイトルディレクトリ
1*、AツリーのサブツリートポロジーがBツリートポロジーと同じかどうか
2、文字列AとBの中で、文字の種類と各文字の出現回数が同じかどうか
3、文字列回転語の問題
4*、文の逆順序の問題
5、文字列の左右シフト問題
6*、最小ディクショナリシーケンス文字をつづる問題
7、スペースの置換問題
8**、最長重複なし文字列問題
二、具体的なテーマの詳細
1、AツリーのサブツリートポロジーがBツリートポロジーと同じかどうか説明:2本の互いに独立したツリーAとBについて、Aに1本のサブツリーがBツリーのトポロジーと完全に同じであるかどうかを確認する.2本の二叉木のヘッドノードAとBを指定し、AにBと同じサブツリーが存在するかどうかを表すbool値を返します.分析:一般的な方法は、Aの各株の木を巡って、Bの木のトポロジー構造と同じかどうかを判断することであり、この方法の時間的複雑度はO(m*n)である.もう1つの優れた解決策は、Aの前順遍歴文字列にBの前順遍歴文字列が含まれているか否かを判断することである.ツリーの問題を文字列の問題に変換し,KMPアルゴリズムで時間複雑度をO(m+n)に下げる.サンプルコード:
public boolean chkIdentical(TreeNode t1, TreeNode t2) {
String t1Str = serialByPre(t1); //
String t2Str = serialByPre(t2);
return getIndexOf(t1Str, t2Str) != -1;
}
// KMP
public int getIndexOf(String s, String m) {
char[] ss = s.toCharArray();
char[] ms = m.toCharArray();
int[] nextArr = getNextArray(ms);
int index = 0;
int mi = 0;
while (index < ss.length && mi < ms.length) {
if (ss[index] == ms[mi]) {
index++;
mi++;
} else if (nextArr[mi] == -1) {
index++;
} else {
mi = nextArr[mi];
}
}
return mi == ms.length ? index - mi : -1;
}
まとめ:ツリーのサブツリーと別のツリーのトポロジーマッチング問題,文字列に変換されたサブストリング問題,古典的なKMPアルゴリズムを用い,時間複雑度O(m+n),空間複雑度O(logn)であった.KMPアルゴリズムはよく使われるアルゴリズムで、KMPアルゴリズムを学ぶ必要があります.
2、文字列AとBのうち、文字の種類と各文字の出現回数が同じかどうかの説明:2つの文字列AとBの場合、AとBの中で出現する文字の種類が同じで、各文字の出現回数が同じであれば、AとBは互いに変形語である.2つの与えられた列が互いに変形語であるかどうかを確認するアルゴリズムを作成してください.2つの文字列AとBとその長さを指定し、互いに変形語であるかどうかを表すbool値を返します.解析:この問題は、補助配列を使用して解決できます.長さ256の整数配列helpを宣言し、文字列Aを1回巡回すると、配列Aの各文字の出現回数を統計し、help配列に記録することができる.次に、文字列Bを巡回し、各文字がhelpの位置に対応する値を1減算し、配列内の値が0未満の場合、AとBは変形語ではなく、そうでない場合、AとBは互いに回転語であることを示す.例コード:要約なし:アシスト配列を使用して問題を解決することは、よく使用される方法です.補助配列は問題を簡略化し,問題の複雑さを低減できる.通常の問題を解決する場合は、配列のほかに、ハッシュテーブル、キュー、スタックなどを補助ツールとして使用して問題を解決します.
3、文字列回転語の問題説明:一つの文字列Aに対して、Aの前の任意の部分を後ろに移動して形成された文字列をAの回転語と呼ぶ.例えばA=「12345」、Aの回転語は「12345」、「23451」、「34512」、「45123」、「51234」である.2つの文字列AとBについて、AとBが互いに回転語であるか否かを判断してください.2つの文字列AとBとその長さlena,lenbを指定し、互いに回転語であるかどうかを表すbool値を返します.解析:Aの文字長をnとします.回転語の構造的特徴により、2つのAを加算して1つの2 n長の文字列Cを得ることができ、C下付き[0...n-1]の任意の位置から長さnの文字列Diを後方に切り取ると、DiはAの回転語である.そして得られたすべてのDi集合には,Aのすべての回転語が含まれている.では,問題をBがCのサブストリングであるかどうかの問題に変換することができる.同様に、KMPアルゴリズムが使用されます.サンプルコード:要約なし:なし
4、文の逆順序問題の説明:文字列について、文字列の単語間で逆順序調整を行うアルゴリズムを設計してください.つまり、文字列はスペースで区切られた部分から構成されており、これらの部分を逆順序にする必要があります.元の文字列Aとその長さを指定し、逆の文字列を返します.テストサンプル:“dog loves pig”、13は結果を返します:“pig loves dog”分析:問題を解く構想は、まず文全体を逆順して、それから各単語を逆順します.各単語を逆順にしてから、文全体を逆順にすることもできます.時間的複雑度はO(n),空間的複雑度はO(1)であった.サンプルコード:
public void rotateWord(char[] chas) {
if (chas == null || chas.length == 0) {return;}
reverse(chas, 0, chas.length - 1);//
int l = -1;
int r = -1;
for (int i = 0; i < chas.length; i++) {
if (chas[i] != ' ') {
l = i == 0 || chas[i - 1] == ' ' ? i : l;
r = i == chas.length - 1 || chas[i + 1] == ' ' ? i : r;
}
if (l != -1 && r != -1) {
reverse(chas, l, r);
l = -1;
r = -1;
}
}
}
まとめ:コードのハイライト部分は、反転するたびに左右の境界を統計するテクニックで、従来のプログラミングで境界を決定するという悩みを解決することができます.
5、文字列の左右シフト問題
説明:文字列の場合、lenの文字列の長さの接頭辞を文字列の最後に平行移動するアルゴリズムを設計します.文字列Aとその長さを指定し、lenを指定すると、平行移動後の文字列を返します.
テストサンプル:
"ABCDE",5,3
結果を返します:DEABC
分析:この問題は前の問題と同じ問題に属し、すべて回転問題である.問題を解くには、まず左右の各部分を回転させ、それから全体を回転させることを考えます.
サンプルコード:なし
まとめ:なし
6、最小ディクショナリシーケンス文字をつづる問題の説明:指定された文字列の配列について、すべての小文字列をつづる大文字列がすべての可能なつづりの中でディクショナリシーケンスが最小になるように、つづり順序を見つけてください.文字列配列strsを指定し、サイズを指定して、つなぎ合わせた列を返します.テストサンプル:["abc","de"],2は結果を返します:“abcde”分析:1つの誤区を解決します---よくこのような問題を解決して1つの誤区に陥ることができて、例えば2つの文字列“b”と“ba”に入って、“b”は“ba”より小さくて、“b”は“ba”の前の“bba”に置くべきで、しかし、正しい順序は“bab”です.この問題を見直し,文字列AとBの前後順を判断する際には,A+BとB+Aの大きさを比較してAとBの前後順を決定すべきである.サンプルコード:
public class MyComparator implements Comparator {
public int compare(String a, String b) {return (a + b).compareTo(b + a); }
}
public String findSmallest(String[] strs, int n) {
if (strs == null || n == 0) {return "";}
Arrays.sort(strs, new MyComparator());//
String res = "";
for (int i = 0; i < n; i++) {
res += strs[i];
}
return res;
}
まとめ:カスタムソートルールを学習します.
7、スペースの置換問題
説明:文字列のスペースをすべて「%20」に置き換える方法を作成します.新しい文字を格納するのに十分なスペースがあり、文字列の真の長さ(1000以下)を知っていると仮定し、文字列が大文字と小文字の英字で構成されることを保証します.string iniStringが元の列であり、列の長さint lenが与えられ、置換されたstringが返される.
試験例:「Mr John Smith」,13
結果を返します:“Mr%20 John%20 Smith”
解析:文字列内のスペースの個数nzeroを最初に取得し、len+2*nzeroの長さの戻り文字配列retを作成します.IniStringの末尾から前への遍歴を開始し、retの末尾に文字を順次入力し、スペースに遭遇した場合、retに%20を挿入します.IniStringを巡回すると、要求に合致する文字列が得られます.
サンプルコード:なし
まとめ:なし
8、最長重複なし文字列問題
説明:文字列の場合、効率的なアルゴリズムを設計し、文字列の最長重複文字のないサブ列の長さを見つけます.文字列Aとその長さnを指定し、その最長の重複しない文字列のサブ列の長さを返します.Aの文字がすべて小文字の英字で、長さが500以下であることを保証します.
試験例:「aabcb」,5
結果を返します:3
解析:変数preと補助配列mapを設定し、preは前の重複文字のないサブ列の開始位置を記録し、mapは文字の出現位置を記録します.preとmapを決定すると、現在の位置文字の最後の重複文字のないサブ列の長さが得られる.
サンプルコード:
public int longestSubstring(String A, int n) {
if (A == null || n == 0) {return 0; }
char[] chas = A.toCharArray();
int[] map = new int[256];
for (int i = 0; i < 256; i++) { map[i] = -1; }
int len = 0; int pre = -1;
int cur = 0;
for (int i = 0; i < n; i++) {
pre = Math.max(pre, map[chas[i]]);
cur = i - pre;
len = Math.max(len, cur);
map[chas[i]] = i;
}
return len;
}
まとめ:文字列内のi位置文字で終わる、重複文字のないサブ列の長さを決定します.preとmap[arr[i]]の2つの値の大きい値に基づいて重複文字列のない左境界を決定し,iを右境界として完成した.