LeetCodeって？
LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。
2022年12月現在2,000問を超える問題が登録されています。
各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。
正誤判定は自動で行われます。
使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。
私はPython3で解いています。
Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量 [ 増井 敏克 ]
問題
タイトル：32. Longest Valid Parentheses
難易度：Hard
内容：
'(' と ')' のみで構成される文字列 s が与えられる。
s の部分文字列のうち、括弧の構成が有効である最も長い文字列の文字数を返す。
例：
Input: s = "(()" Output: 2 ※最も長い有効な部分文字列は"()"
Input: s = ")()())" Output: 4 ※最も長い有効な部分文字列は"()()".
Input: s = "" Output: 0
回答
day11 でやったように、スタックを使って解いていきます。
解法
左括弧が来たらスタックに詰め、右括弧が来たらスタックから左括弧を取り出しペアとします。
この時ペアとなった部分は有効になるので、有効である文字列部分を記憶しておき、どこが最長かを探せばいいわけです。
” ) ( ( ) ) ) “を例に考えてみます。
有効な文字列部分（インデックス）の探索
０．いきなり右括弧が来ています。これは破棄して次に行きます。
１．２．左括弧が来たのでスタックに詰めます。この時この文字列 s 中のインデックス 1, 2 をスタック上で記録しておきます。
３．４．右括弧が来たのでスタックの左括弧を取り出してペアとします。この時、インデックス 2, 3 と1, 4 を有効文字列のインデックスとして保管します。
5．最後に左括弧が来たのでスタックに詰めて完了です。
有効な最長部分文字列の探索
文字列 s 中の有効である部分のインデックスが分かったので、今度は最長の部分文字列を探索します。
これは簡単で、有効文字列のインデックスをソートし、最も長い連番になるものを探せば求まります。
例えば [1, 2, 7, 8, 5, 6] をソートすると [1, 2, 5, 6, 7, 8] となるので最も長い連番は 5 ～ 8 で長さは 4 です。
コード
上記の理論をコードにします。
class Solution:
def longestValidParentheses(self, s: str) -> int:
valid = [] # 有効文字列のインデックス
stack = [] # 左括弧のインデックスを入れるスタック
for i, l in enumerate(s):
if l == "(": # 左括弧であれば
stack.append(i) # スタックに詰める
else: # 右括弧であれば
if len(stack) > 0: # スタックが空でなければ
valid.append(stack[-1]) # 有効文字列のインデックスに左括弧のインデックスを追加
stack.pop(-1) # スタックをポップ
valid.append(i) # 効文字列のインデックスに右括弧のインデックスを追加
valid.sort() # 有効文字列のインデックスをソート
max_len = tmp_len = 0 # 見つかった最長文字列長と、探索用文字列長を初期化
for i in range(len(valid) - 1):
if valid[i] + 1 == valid[i + 1]: # 連番になっていれば
if tmp_len == 0: # 探索用文字列長が0（最初の文字）ならば
tmp_len += 1
tmp_len += 1
max_len = max(max_len, tmp_len) # 最長を更新していれば更新
else: # 連番でなければ
tmp_len = 0 # 探索用文字列長を初期化
return max_lenコードはgithubにも保管しています。
結果
コメント