leetcode : Valid_Parentheses - かずとよのアウトプット日記

こんにちは、かずとよです。

今回もleetcode。

まずは問題文が以下。

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

Input: s = "{[]}"
Output: true

Constraints:

1 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.

簡単に解読すると

【与えられる文字列は、"(", ")", "{", "}", "[", "]"　これら3種類の括弧のみ。

正しく使えているか判別しよう。】

ということみたい。

例1）"("　は　")"　で閉じるのは、もちろんOK。

例3）"("　を　"]"　で閉じるのはダメ。

例4）最初と閉じとがおかしい。

みたいな感じですね。

ぶっちゃけ今回の問題、昨日から始めたのに、解けなさすぎて頭痛がやばくなって寝ました。

で、一旦コードから離れて、リフレッシュして、再挑戦！

・・・それでも解けなくて、他の人のコード見ました。

理解するまで読み込んで、勉強しました。

やっと理解できて自分でコード書けたので、アウトプット！

まずは、僕が最初書いてた、ダメダメコード↓↓

def is_valid(s)
    x = s.match(/(\((\]|\}))|(\[(\)|\}))|(\{(\)|\]))/)
    y = s.match(/\(\)|\[\]|\{\}/)
    z = s.match(/\)\(|\]\[|\}\{/)
    start_c = s.count("([{")
    end_c = s.count(")]}")
    if s.length == 1
      return false
    elsif x.to_s.length >= 2
      return false
    elsif y == nil
      return false
    elsif z.to_s.length >= 2
      return false
    elsif start_c == end_c
      return true
    end
end

ここまで、10回以上トライアンドエラーを繰り返してます。

ひとつクリアできても、次に出てくるテスト内容で引っかかるから、elseif増やして・・・みたいな感じで。

この後も、複数回これを繰り返しました。ほんとキリがないし、どんどんと見るに耐えないコードになっていってしまったので、挫折。

他の方があげてるコードを見て勉強し、自分なりに解釈して書いたコードが以下。

def is_valid(s)
  stack = []
  s.each_char do |c|
           # 渡された文字列を一文字ずつ繰り返し
    case c
           # cを以下の条件で振り分け
    when "(", "{", "["
           # 開始の括弧なら
      stack << c
           # cを配列へ。
#---------------------------------------①
    when ")"
           # ）なら
      if stack.pop != "("
           # popメソッドで配列の最後を消しつつ、その要素が（じゃなければ
        return false
      end
#---------------------------------------①
#---------------------------------------①と同じ
    when "}"
      if stack.pop != "{"
        return false
      end
#---------------------------------------①と同じ
#---------------------------------------①と同じ
    when "]"
      if stack.pop != "["
        return false
      end
#---------------------------------------①と同じ
    end
  end
  return stack.empty?
           # 配列は空？→空ならtrue、何かあればfalse(空ということは、開始の括弧と閉じ括弧が同数)
end

まっっっったく違います。笑

まずは、最初僕が書いてたコードについて。

僕は何故か、正規表現を使いこなせば、コードを短く済ませる事ができるんじゃないか？と考えてしまいました。（正規表現使いこなせるのカッコイイから憧れてます）

その変なこだわりのせいで、目を酷使して、結果、頭痛くなったんだと思います。笑

正直、他の方のコードを参考にする数回前の失敗時点で、無理じゃね？って思ってたので、その段階で諦めて一旦まっさらの状態からスタートするべきだったかもしれません。

で、別の方のコードを参考にしたコード。

まず、popというメソッド。このコードの存在を知れた事がかなり大きかったです。

配列の最後の要素を消しつつその消した要素を扱えるとは・・・

今までの僕だと、stack[-1]で扱って、その後にdelete_atで消すとかしか発想がなかったので。

ほんと、知識は力だと思いました。

＊今回の学び:

書いていったコードがダメかもしれないなって思ったら、一旦捨ててみたほうが良いかもしれない。自分の最初の発想に囚われない。
理解するためなら、他の方のコードは見た方がいい
popメソッドは、配列の最後の要素を消す。その際、消した要素を返す。
each_charでは、文字列を一文字ずつ繰り返し処理。
caseは、オブジェクトを指定し、後に書くwhenの条件にヒットしていたら、次のwhenかendまでの処理を実行する。