LeetCode問題解(0678):ワイルドカード*を含む文字列のカッコが有効かどうかを判断する(Python)

テーマ:原題リンク(中等)
ラベル:文字列、欲張りアルゴリズム
解法
時間の複雑さ
くうかんふくざつさ
実行時間
Ans 1 (Python)
O ( N ) O(N) O(N)
O ( N ) O(N) O(N)
24ms (100.00%)
Ans 2 (Python)
O ( N ) O(N) O(N)
O ( 1 ) O(1) O(1)
36ms (87.80%)
Ans 3 (Python)
LeetCodeのPython実行用は,時間の複雑さに明らかな差がない限り,実行用は一般的に同じレベルであり,参考意義としてのみ用いられる.
解法一(シナリオシミュレーション):
[外部チェーン画像の転送に失敗し、ソース局に盗難防止チェーン機構がある可能性があり、画像を保存して直接アップロードすることを提案する(img-TvCqyEYc-15976498387889)(LeetCode題解(0678):スクリーン1.png)

class Solution:
    def checkValidString(self, s: str) -> bool:
        stack = []
        for ch in s:
            if ch == ")":
                idx = len(stack) - 1
                while idx > -1:
                    if stack[idx] == "(":
                        break
                    idx -= 1
                if idx >= 0:
                    stack.pop(idx)
                elif len(stack) > 0:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(ch)

        left_num = 0
        for ch in stack:
            if ch == "(":
                left_num += 1
            elif left_num > 0:
                left_num -= 1
        return left_num == 0

解法二(欲張りアルゴリズム):

class Solution:
    def checkValidString(self, s: str) -> bool:
        min_left_num = 0
        max_left_num = 0
        for ch in s:
            if ch == "(":
                min_left_num += 1
                max_left_num += 1
            elif ch == "*":
                if min_left_num > 0:
                    min_left_num -= 1
                max_left_num += 1
            else:
                if min_left_num > 0:
                    min_left_num -= 1
                max_left_num -= 1
            if max_left_num < 0:
                return False
        return min_left_num == 0