# LeetCode Easy 14. Longest Common Prefix

tags: leetcode

問題

• Explore
• Problems

アイデア

｢複数の文字列から，共通する最長の接頭辞を探せ｣という問題です．ない場合は空の文字列を返せば良いようです．

2文字列を比較して設備時を探す，これを全ての文字列に対して行うという2つの問題に分割出来ることを使います．

解法

• 2つの文字列を比較して共通する最長の接尾辞を返す関数get_common_prefixを書きます．
• これを配列の全ての要素に左から適用するreduce関数を使います．

計算量

文字列の個数が$N$，文字列の大きさが最小で$S$とします．

• 時間計算量
  • $O(NS)$
• 空間計算量
  • $O(1)$

Python

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def get_common_prefix(s: str, t: str) -> str:
            common_length = 0

            for  i in range(0, min(len(s), len(t))):
                if s[i] != t[i]:
                    break
                common_length += 1
            
            return s[:common_length]
        
        if not strs:
            return ""
        
        return reduce(get_common_prefix, strs)