概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day46「406. Queue Reconstruction by Height」
今はTop 100 Liked QuestionsのMediumを解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。
Twitterやってます。
問題
難易度は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なのでそこまで難しいと言える内容ではなかったですが、頭の運動としては楽しかったので解いてみることをお勧めします。
特に解説すべきことがない・・・
では箸休めの問題ですし今回はここまで。
お疲れ様でした。