【LeetCode】就活に向けたコーディングテスト対策 #05

はじめに

こんばんは．
M1就活生がLeetCodeから，easy問題を中心にPythonを用いて解いていきます．

↓では，解いた問題のまとめを随時更新しています．
まとめ記事

問題

今回解いたのは，難易度easyから 問題14のLongest Common Prefix です．
問題としては，入力として与えられる文字列の配列の中から，最長の共通の接頭辞を持つ文字列を見つけるというもの．

入力例と出力例は以下の通りです．

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

なお，この問題は文字列のペア間ではなく，配列中の全ての文字列が対象とのことです．
例えば，入力配列が ["a", "a", "b"] なら "" を返します（"a" ではない）．

書いたコード

とりあえず，思いついたままに書いてみました．

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = ""
        flag = True
        for i in range(len(strs)):
            prefix_candidate = strs[0][i]
            for str_element in strs[1:]:
                if str_element[i] != prefix_candidate:
                    flag = False
                    break
            if flag:
                prefix += prefix_candidate
        return prefix

入力配列strsの先頭文字列の要素を順に接頭辞候補とします．接頭辞候補を，残りの文字列の同じ位置の要素と同じかどうか走査していくことで，接頭辞を見つけます．

しかし，このままではリストの範囲外を参照してしまうのと，接頭辞が異なる判定となった場合も，文字列の最後の要素まで走査してしまいます．そのため，入力配列strs中に含まれる文字列の最低文字数を繰り返しの範囲とし，flagがFalseであれば，走査を終了する判定を追加しました．

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = ""
        flag = True
        for i in range(len(min(strs))):
            prefix_candidate = strs[0][i]
            for str_element in strs[1:]:
                if str_element[i] != prefix_candidate:
                    flag = False
                    break
            if flag:
                prefix += prefix_candidate
            else:
                break
        return prefix

内側の繰り返しでも，明示的に繰り返し回数を指定してあげたほうがリーダブルかつ効率的かも...？

おわりに

LeetCodeでは，Testcaseがいくつか用意されているようですが，今回のようにたまたまうまく動いた場合もあるみたいです（上側のコード）．例外的なケースにも対応できるコーディングを意識していきたいと思いました．

今回書いたコードはGitHubにもあげておきます．

前回　次回