Zenn
🐈

LeetCode #14. Longest Common Prefixやってみた

に公開
JavaScript
LeetCode
tech

問題 (Easy)

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".
→ 詳細

問題を理解する (5分)

文字列が入った配列を受け取り、そのすべての要素の中の文字列の始まりが共通である最長の文字を返す。
例）
Input: strs = ["flower","flow","flight"]
Output: "fl"

解き方を日本語で組み立てる (10分)

  1. forEachで配列の要素を分解する
  2. 配列の要素1つ目の文字列をforで一つずつ文字を抜き取る
  3. searchTermという変数に、取得した１文字を足していく
  4. もし、forEachで分解したすべての配列の要素の値に、searchTermが含まれていたら、continue。(indexOf)で検索する
  5. 含まれていなかったら、そのsearchTermを返す

考えた解き方をJavaScriptコードで表現する (15分)

forEachが使えなかった

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let firstStr = strs[0];
    let searchTerm = '';

    // 2. 配列の要素1つ目の文字列をforで一つずつ文字を抜き取る
    for(let i = 0; i < firstStr.length; i++){
         3. searchTermという変数に、取得した１文字を足していく
        searchTerm += firstStr[i];

    // 3. strsの配列の各要素の値に、searchTermが含まれていたら、continue。(indexOf)で検索する
        if(strs[1].indexOf(searchTerm) == 0 && strs[2].indexOf(searchTerm) == 0){
            continue;
        } else {
            // 4. 含まれていなかったら、含まれていない文字を除いてsearchTermを返す
            return searchTerm.slice(0, -1);
        }
    }
};

引数にある配列の要素を回して、searchTermが入っているかどうかを確認したかった。しかし以下の原因があって実現できなかったと考える。

indexが0の要素だけ例外に処理をしないといけなかった。

strsのindexが0の要素だけ、中身の文字列をfor文で回して比較対象となるsearchTermを定義づけなければならなかった。strs.forEachとしたかったのだが、それだとindexが0の要素も処理されてしまう。

searchTermを定義づけた後、他のstrsの要素の中身と比較する必要があった

strs[0]の文字の要素を回すfor文の中で、strsの要素を回すforEach構文を書くことができなかった。strs[0]の文字数分forEachが回る構造になるから。

forEachは途中で処理を止められない

searchTermが含まれているかどうかを見たときに、その条件結果によって、処理を止めたりができない

解決！every構文というものがあった！ (神！)

Array.prototype.every();

every() は Array インスタンスのメソッドは、列内のすべての要素が指定された関数で実装されたテストに合格するかどうかをテストします。これは論理値を返します。

私が考えたコード↓

お、珍しくコードが少ない…！
ここ最近、プロタイプメソッドを学習したから、メソッドを使ってみた！

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let firstStr = strs[0];
    let searchTerm = '';
    
    for(let i = 0; i < firstStr.length; i++){
        searchTerm += firstStr[i];

        if(strs.every(str => str.indexOf(searchTerm) === 0)){
            continue;
        } else {
            return searchTerm.slice(0, -1);
        }
    }

    return searchTerm;
};

今回使ったプロトタイプメソッド

everyメソッド

every() は Array インスタンスのメソッドは、列内のすべての要素が指定された関数で実装されたテストに合格するかどうかをテストします。これは論理値を返します。

Array.prototype.every()

indexOfメソッド

indexOf() は String 値のメソッドで、この文字列を検索し、指定した部分文字列が最初に出現するインデックスを返します。

String.prototype.indexOf()

sliceメソッド

slice() は Array インスタンスのメソッドで、配列の一部を start から end （end は含まれない）までの範囲で、選択した新しい配列オブジェクトにシャローコピーして返します。

Array.prototype.slice()

ChatGPTにリファクタリングしてもらった

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {

    // 1. 最初の文字列（strs[0]）の各文字を順番にチェックする
    for (let i = 0; i < strs[0].length; i++) {
        // 2. 現在のインデックスにある文字を char に代入
        const char = strs[0][i];
         // 3. 配列の2番目以降の文字列を順にチェックする
        for (let j = 1; j < strs.length; j++) {
            // 4. もし現在のインデックスにある文字が、strs[0]の文字列と一致しなければ
            if (strs[j][i] !== char) {
                // 5. 一致していた直前までの部分をプレフィックスとして返す
                return strs[0].slice(0, i);
            }
        }
    }

    return strs[0];
};

気づき

  • strs[0]の文字列を回す繰り返し処理の中に、strsの要素を回す繰り返し処理を書くことができないと思っていたが、これはそれを実現している
  • 私のコードでは、一致した文字列を変数にいちいち代入していたが、一文字ずつ比較している。
  • なるほどなあと思ったのは、strs[j][i]のところ。うまく、for文のインデックスを使って、strs[1]以降の配列の文字列の、strs[0]の文字列と同じ○番目が同じかどうかを比較している。

反省

メソッドを使う前提でコードを書き始めてしまったため、インデックスをうまく利用することができなかった。また、indexOfを使うために比較した文字列を保持しておく変数を持っておく必要が出てしまった。

ChatGPTにもコードを書かせてみる

解法1: 文字列をソートして最初と最後を比較

辞書順でソートした後、最初と最後の文字列だけを比較すれば十分です。

var longestCommonPrefix = function(strs) {
    if (!strs.length) return "";
    strs.sort();
    let first = strs[0], last = strs[strs.length - 1];
    let i = 0;
    while (i < first.length && first[i] === last[i]) {
        i++;
    }
    return first.slice(0, i);
};

気づき

この考えはなかったなあ。
ソートして、最初と最後の文字列だけを比較している。
でも、ソートする必要がある？結局は全部が揃ってないといけないから、意味あるかなと思って、ソートする理由を聞いてみた

ソートされた配列では、似ている文字列が隣り合うように並びます。
その中でも**最初と最後の文字列が一番遠くなる（＝最も差が大きい）**ため、
この2つの共通接頭辞が他のどのペアよりも短くなりやすいです。
つまり：最初と最後の文字列が一致する範囲は、全体の共通接頭辞の限界です。

なるほど！ソートすることで、1番違う文字列とを比較することができるのか。
わーこの視点はなかった。面白い。

使われているプロトタイプメソッド

sort

sort() は Array のメソッドで、配列の要素をその場 (in-place) でソートし、ソートされた同じ配列の参照を返します。既定のソート順は昇順で、要素を文字列に変換してから、 UTF-16 コード単位の値の並びとして比較します。

Array.prototype.sort()

解法2：すべての文字列に対して段階的に共通接頭辞を縮めていく

最初の文字列を初期値として、他の文字列と共通部分だけを残していく方法。

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (!strs.length) return "";
    return strs.reduce((prefix, str) => {
        let i = 0;
        //prefix = コールハック関数の返値
        //str = コールバック関数の初期値

        //prefixと同じindexdがstrと同じindexの1文字が同じ間、次の文字を見ていく
        while (i < prefix.length && i < str.length && prefix[i] === str[i]) {
            i++;
        }
        // 一致していた直前までの部分をプレフィックスとして返す
        return prefix.slice(0, i);
    });
};

気づき

  • reduceメソッドを使って、コールバック関数を使っている。これによって、「前の結果に対して次の処理をする」という構造が簡潔にできる

使われていたプロトタイプメソッド

reduceメソッド

reduce() は Array インターフェイスのメソッドで、配列のそれぞれの要素に対して、ユーザーが提供した「縮小」コールバック関数を呼び出します。その際、直前の要素の計算結果の返値を渡します。配列のすべての要素に対して「縮小」コールバック関数を実行した最終結果は、単一の値となります。

Array.prototype.reduce()

どれがいいんだ？

ChatGPTはそれぞれのアプローチをこうまとめた

アプローチ 特徴 早期終了 可読性 スピード感
for文 明示的で制御しやすい あり 高い 高い
sort + 比較 計算量少なめ、最小比較 なし 中 中
reduce 段階的縮小、シンプルな設計 なし 高い 中

sort+比較がいいと思う。

for文とreduce文は、strsのすべての要素と比較しているのに対して、sortを使ったアプローチでは、ソートした後の配列の要素の最初と最後である文字列（＝1番かけ離れている文字列）の2つの要素しか比較していない。→ 渡されるstrsの要素が増えても、早く処理できる。

まとめ

このアクティビティで1番面白いポイントは、ChatGPTを使って、自分のコードをリファクタリングする瞬間、いろんな解法を知れる瞬間。新しい知識と気づきが一気に入ってくる。
次は、メソッドを使う前に基本構文で書いてみて、リファクタリングとしてメソッドを活用する流れでやってみようと思う。

Discussion