概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインでだそうです。
その対策としてLeetCodeなるサイトで対策を行うようです。
※LeetCodeとは
本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトです。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていきます。
問題
この問題は文字列の配列strsが与えられたときに、その配列内のすべての文字列に共通して現れる最も長い先頭部分を見つけて返すもの。
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.
Constraints:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters if it is non-empty.
解法
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
prefix = strs[0]
for i in range(1, len(strs)):
while strs[i].find(prefix) != 0:
prefix = prefix[:-1]
if not prefix:
return ""
return prefix
初期化
prefix = strs[0]
strsリストの最初の文字列を共通接頭辞の候補として設定する。
これは全ての文字列がこの接頭辞を持つかどうかをチェックする要素である。
文字列の比較
while strs[i].find(prefix) != 0:
現在の文字列 strs[i]の中でprefixが最初に現れるインデックスを返す。
共通する文字列が見つかるまでループする。
prefix = prefix[:-1]
prefixが共通接頭辞ではないと判断された場合、prefix の最後の文字を1文字削除する。
これによりより短い接頭辞を試す。
if not prefix:
return ""
prefixが空文字列になってしまった場合 (not prefix が True の場合)、共通する接頭辞が存在しないので空文字列を返す。
例
Input: strs = ["flower","flow","flight"]
| strs[i] | prefix（開始時） | prefix（更新後） |
|---|---|---|
| -（初期化） | "flower" | "flower" |
| "flow" | "flower"（共通しない） | "flowe" |
| "flow" | "flowe"（共通しない） | "flow" |
| "flow" | "flow"（共通する→次のインデックスへ） | "flow" |
| "flight" | "flow"（共通しない） | "flo" |
| "flight" | "flo"（共通しない） | "fl" |
| "flight" | "fl"（共通する） | "fl" |
最終的にprefixは"fl"となる。
Discussion