ゼロから始めるLeetCode Day47 「14. Longest Common Prefix」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
[ゼロから始めるLeetCode Day46「406. Queue Reconstruction by Height」
次回
ゼロから始めるLeetCode Day48 「26. Remove Duplicates from Sorted Array」

Twitterやってます。

問題

14. Longest Common Prefix

難易度はEasy。
箸休め的に解いた問題なのでそこまで難しくはないかもしれません。

問題としては、与えられた文字列の配列において、それぞれの文字列の中で最も長い共通部分を返すような関数を設計する、というものです。
仮に何も共通部分がない場合は""を返します。

Input: [“flower”,“flow”,“flight”]
Output: “fl”
Example 2:

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

解法

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        ans = ""
        for num in zip(*strs):
            if len(set(num)) == 1:
               ans += num[0] 
            else:
                return ans
        return ans
# Runtime: 32 ms, faster than 74.42% of Python3 online submissions for Longest Common Prefix.
# Memory Usage: 14.1 MB, less than 22.07% of Python3 online submissions for Longest Common Prefix

zip関数を使って解きました。
Easyなのでそこまで難しいと言える内容ではなかったですが、頭の運動としては楽しかったので解いてみることをお勧めします。

特に解説すべきことがない・・・

では箸休めの問題ですし今回はここまで。
お疲れ様でした。