Pythonで同じ最初の文字を持つ連続する単語の最長列を見つける方法

問題の概要

すべて小文字で構成された単語のリストが与えられたとき、先頭の文字が同じである連続する部分リストの中で最も長いものの長さを求めることを考えます。

例えば、入力が ["she", "sells", "seashells", "on", "the", "seashore"] の場合、出力は 3 になります。これは、「she」「sells」「seashells」という3つの連続する単語がすべて同じ先頭文字「s」を持っているためです。

解決のアプローチ

この問題は、リストを一度走査しながら「現在注目している先頭文字」と「その文字が続いている長さ」を追跡することで効率的に解けます。具体的な手順は以下の通りです。

• 最大長を記録する変数 maxlength を 0 で初期化します。
• 現在の先頭文字 curr_letter を Null(未設定)、現在の連続長 curr_length を 0 で初期化します。
• リスト内の各単語について次の処理を行います。
  • curr_letter が未設定、または現在の単語の先頭文字と異なる場合:
    • maxlength を maxlength と curr_length の大きい方で更新します。
    • curr_letter を新しい単語の先頭文字に更新し、curr_length を 1 にリセットします。
  • それ以外の場合(先頭文字が同じ場合):
    • curr_length を 1 増やします。
• ループ終了後、maxlength と curr_length の大きい方を返します。

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution:
    def solve(self, words):
        maxlength = 0
        curr_letter, curr_length = None, 0
        for word in words:
            if not curr_letter or curr_letter != word[0]:
                maxlength = max(maxlength, curr_length)
                curr_letter, curr_length = word[0], 1
            else:
                curr_length += 1
        return max(maxlength, curr_length)
ob = Solution()
words = ["she", "sells", "seashells", "on", "the", "seashore"]
print(ob.solve(words))

入力

["she", "sells", "seashells", "on", "the", "seashore"]

出力

3

計算量について

このアルゴリズムはリストを一度だけ走査するため、時間計算量は O(n)(n は単語数)、追加の記憶領域も定数個の変数のみで済むため、空間計算量は O(1) となります。非常にシンプルかつ効率的な手法です。