こちらは「Longest Comman Prefix」のPythonによる解答例となっております。この問題は、複数の文字列が与えられたときに、それらの先頭に共通する部分列を返す問題です。
問題
文字列の配列 strs が与えられたとき、それらの先頭に共通する最長の部分列を返します。もし共通の部分列が存在しない場合は、空文字列 “” を返します。
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]は小文字の英字のみから構成されます。
解法
この問題は、簡単な文字列操作を用いた1つのアプローチがあります。
アルゴリズムの概要を以下に述べます。
- 最短の文字列を取得します。
- 最短の文字列の各文字について、他のすべての文字列に存在するかどうかを確認します。
- 存在する場合は、その文字を答えの文字列に追加します。
- 存在しない場合は、処理を終了します。
Pythonコード
以下のコードが、「Longest Common Prefix」を解くためのPythonプログラムとなります。
### Function ##################################################################
def solve(num=0):
solver = Solution().longestCommonPrefix
if 1 <= num <= Input().input: id_LIST = [num]
else: id_LIST = [id+1 for id in range(Input().input)]
for id in id_LIST:
data = Input(id)
ans = solver(data.strs)
result = "OK" if ans==data.ans else "NG"
print(f"[{str(id).zfill(3)}] {result}")
### Class #####################################################################
class Solution:
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]: Lowercase Alphabets
:rtype: str
"""
if len(strs)==1: return strs[0]
prefix = ""
for i in range(len(min(strs))):
c = strs[0][i]
if all(a[i]==c for a in strs): prefix += c
else: break
return prefix
#==============================================================================
class Input:
def __init__(self, num=0):
if num == 1:
self.strs = ["flower","flow","flight"]
self.ans = "fl"
elif num == 2:
self.strs = ["dog","racecar","car"]
self.ans = ""
else:
self.input = 2
### Main ######################################################################
if __name__ == "__main__":
solve()
###############################################################################