最長共通接頭辞

説明#

文字列の配列から最長の共通接頭辞を見つける関数を作成します。

共通の接頭辞が存在しない場合は、空の文字列 "" を返します。

例 1:

入力: ["flower","flow","flight"]
出力: "fl"

例 2:

入力: ["dog","racecar","car"]
出力: ""
説明: 共通の接頭辞は存在しません。

注意:

すべての入力は小文字のアルファベット a-z のみを含みます。

アプローチ#

特殊なケース：配列が空の場合は、"" を返します。配列の要素が 1 つだけの場合は、その要素を直接返します。
最初の文字から始めて、各要素の最初の文字が最初の要素と同じかどうかを判断し、次に 2 番目の文字を判断します。
- 特殊なケース：
  1. 現在の文字が空の場合：文字を前から順に判断しているため、現在の文字列が最も短いことがわかりますので、その要素の文字列を直接返します。
  2. 現在の文字が最初の要素の現在の位置の文字と異なる場合：最初の要素の現在の位置の文字を '\0' に切り取り、最初の要素を返します。

char * longestCommonPrefix(char ** strs, int strsSize){
    if(strsSize == 0 )//空の配列を返す
        return "";
    if(strsSize == 1)//1つの文字列を直接返す
        return strs[0]; 
    for(int i=0;;i++) {//j列目のi番目の文字
        for(int j=0;j<strsSize;j++) {
            if(strs[j][i] == 0)//空の場合は現在の文字列を返す
                return strs[j];
            if(strs[0][i] != strs[j][i]) {//最初の要素と異なる場合、最初の要素を切り取って返す
                strs[0][i] = '\0';
                return strs[0];
            }   
        }
    }
}

注意点#

最初は列ごとに検索し、異なる要素を切り取って返すことしか思いつきませんでしたが、デバッグ中に特殊なケースの特殊な処理を発見しました。