3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-06-05

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

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

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

Leetcode

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day46「406. Queue Reconstruction by Height」

今はTop 100 Liked QuestionsのMediumを解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。

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なのでそこまで難しいと言える内容ではなかったですが、頭の運動としては楽しかったので解いてみることをお勧めします。

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

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

3
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?