序文集
コードリポジトリ
GitHub: github.com/...
Gitee: gitee.com/inwsy/LeetC...
問題: 最も長い公開接頭辞
問題ソース
文字列の配列の中で最も長い共通の接頭辞を見つける関数を書いてください。
共通の接頭辞が存在しない場合は、空の文字列 "" を返します。
例 1.
: ["flower","flow","flight"]
: "fl"
例 2：
: ["dog","racecar","car"]
: ""
: 入力には共通の接頭辞がない。
説明
すべての入力は小文字のa-zのみを含みます。
解答A：「暴力的な水平検索
この問題を見たとき、「もう一回やってもいいかな」という気持ちになります。 まず、「答えを見ていない」という発想についてですが、この発想はこの問題を見たときに普通の人が持つべきものだと思います。この発想がない人は、もしかしたら芸術系の勉強に向いているのかもしれません。
このアイデアはシンプルで、暴力的で、直接的なので、誰もが最初にこのプログラムを思い浮かべることができるはずです。
次はコードタイムです：
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
prefix = compareTwoStrs(prefix, strs[i]);
if (prefix.length() == 0) break;
}
return prefix;
}
// 2つの文字列の共通の接頭辞を取得する
private String compareTwoStrs(String str1, String str2) {
int length = Math.min(str1.length(), str2.length());
int index = 0;
while (index < length && str1.charAt(index) == str2.charAt(index)) {
index++;
}
return str1.substring(0, index);
}
私はLeetCodeで実行し、直接この結果を取得し、この結果は、私はLeetCodeの結果を行うには最高のはずですが、驚くべきことに、時間は1ミリ秒未満を要し、私はとても牛革されている、私は浮遊している感じです。
私は自信を持って答えのページを開き、私はBの時間をふりをする返信を書く準備ができていた、私は唖然とした、NMは、この質問は、実際にはああ、心の崩壊のように多くの種類のソリューションを持っています。
解答B：「激しい縦検索
私の上記のような考え方の答えは、「暴力的な水平検索」と呼ばれ、その後、この考え方に沿って神々を見て、「暴力的な垂直検索」を思い付きました。
絵は書きたくないのですが、考え方は上と同じで、横の比較を縦の比較に置き換えて、最短の文字列の長さが終わるか、違う文字が出現し始めるまで、円より次々と。
このようにコードアップします：
public String longestCommonPrefix_1(String[] strs) {
if (strs.length == 0) return "";
for (int i = 0; i < strs[0].length(); i++) {
for (int j = 1; j < strs.length; j++) {
if (i == strs[j].length()
strs[j].charAt(i) != strs[0].charAt(i)) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}
解答C : "パーティショニング
ここで終わったと思い、解答までスクロールしてみると、やはり間違っていて、「覇権」と「偉大」という言葉を甘く見ていたことがわかりました。
分割」の図式は、まず文字列配列を真ん中から切断し、切断後の2つの配列の接頭辞のうち最も長いものを「暴力的横探し」の図式に従って取り出し、最後にその2つの接頭辞の交点を取り出すというもの。
このスキームは、以下に示すように、「暴力的な水平検索」スキームの変形として見ることができます：
public String longestCommonPrefix_2(String[] strs) {
if (strs.length == 0) {
return "";
} else {
return longestCommonPrefix(strs, 0, strs.length - 1);
}
}
public String longestCommonPrefix(String[] strs, int start, int end) {
if (start == end) {
return strs[start];
} else {
int mid = (end - start) / 2 + start;
String lcpLeft = longestCommonPrefix(strs, start, mid);
String lcpRight = longestCommonPrefix(strs, mid + 1, end);
return commonPrefix(lcpLeft, lcpRight);
}
}
public String commonPrefix(String lcpLeft, String lcpRight) {
int minLength = Math.min(lcpLeft.length(), lcpRight.length());
for (int i = 0; i < minLength; i++) {
if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
return lcpLeft.substring(0, i);
}
}
return lcpLeft.substring(0, minLength);
}
もちろん、このスキームは、「ブルートフォース水平検索」を「ブルートフォース垂直検索」に置き換えることで、さらに変化させることができます。
解決策D：「二分探索
最後に、比較的新しく、問題をブラッシュアップしていない人には思いつかないであろう二分探索です。
これは、文字列配列中の最長の共通接頭辞の長さが、文字列配列中の最短文字列の長さを超えないようにするというものです。
まず、最も短い文字列の長さ minLength を求め、その minLength が最長の共通接頭辞かどうかを判断するためにランダムに文字列を見つけ、そうでなければ分割の途中から minLength を求め、共通接頭辞の前半かどうかを判断し、そうであれば最長の共通接頭辞はこの半分以上でなければならず、そうでなければ最長の共通接頭辞は半分以下でなければならない、というように徐々に範囲を狭めていきます。もしそうでなければ、最長の共通接頭辞はこの半分以下でなければならず、このように徐々に範囲を狭めていき、見つけるまで続けます。
この絵は描きません。単純な二分法で、当たるまでどんどん削っていくのです。
public String longestCommonPrefix_3(String[] strs) {
if (strs.length == 0) return "";
// 最初に最小の長さを得る
int minLength = Integer.MAX_VALUE;
for (String str : strs) {
minLength = Math.min(minLength, str.length());
}
// 変数を定義し、二分法を開始する
int low = 0, high = minLength;
while (low < high) {
// 中間点を取得する
int mid = (high - low + 1) / 2 + low;
if (isCommonPrefix(strs, mid)) {
low = mid;
} else {
high = mid - 1;
}
}
return strs[0].substring(0, low);
}
public Boolean isCommonPrefix(String[] strs, int length) {
// まず、比較する文字列の前半を取得する
String str0 = strs[0].substring(0, length);
for (int i = 1; i < strs.length; i++) {
for (int j = 0; j < length; j++) {
// 文字による判断は、異なる文字がある場合は直接返す false
if (str0.charAt(j) != strs[i].charAt(j)) {
return false;
}
}
}
return true;
}
上の結果を見ると、二分法が一番遅いように見えますが、実はこれはテスト用のデータセットによるもので、テストに使ったデータセットの方が「暴力的水平探索」方式に適しているかもしれません。
