アルゴリズム問題(22/08/12)

今日は以下の問題を解きました。

問題

リンク

20. Valid Parentheses
https://leetcode.com/problems/valid-parentheses/submissions/

自分の書いたコード

# @param {String} s
# @return {Boolean}
def is_valid(s)
    return false if s.length % 2 == 1

    s_a = s.chomp.split("")
    new_string = ""
    
    s_a.each_with_index do |char, index|
        last_char_of_new_string = new_string[-1]
        
        if index == 0 || char == "(" || char == "[" || char == "{"
            new_string = new_string.concat(char)
            
        # elsif char == "(" || char == "[" || char == "{"  
        else
            if char == ")"
                if last_char_of_new_string != "("
                    return false
                else
                    new_string = new_string.chop
                end
            elsif char == "]"
                if last_char_of_new_string != "["
                    return false
                else
                    new_string = new_string.chop
                end
            elsif char == "}"
                if last_char_of_new_string != "{"
                    return false
                else
                    new_string = new_string.chop
                end
                
            end
        end
    end
    
    if new_string == ""
        return true
    else
        return false
    end
end

使用したメソッド

String#chop: 文字列の最後の文字を取り除いた新しい文字列を生成して返す(String#chop (Ruby 3.1 リファレンスマニュアル))
String#[]: 文字列からn番目の要素を返す。今回は最後の要素を取得するときに取得(String#[] (Ruby 3.1 リファレンスマニュアル))
String#concat: 文字列を連結する。'abc'<< 'def' のような感じでもできる(Rubyの文字列連結に関して知っておくべきこと - Qiita)

解答例(Discussから引用)

ここをクリック

一覧用のリンク
https://leetcode.com/problems/valid-parentheses/discuss/?currentPage=1&orderBy=most_votes&query=&tag=ruby

1. https://leetcode.com/problems/valid-parentheses/discuss/491448/Simple-Ruby-solution
とてもシンプルでわかりやすい。そして短い。
stackという命名はすごい。
またempty?メソッドを使ってtrue, falseを1行で返しているのがすごい。

Runtime: 24 ms, faster than 99.57% of Ruby online submissions for Valid Parentheses.
Memory Usage: 9.3 MB, less than 100.00% of Ruby online submissions for Valid Parentheses.

# @param {String} s
# @return {Boolean}
def is_valid(s)
    return true if s.empty?
    
    stack = []
    s.each_char do |c|
        case c
        when '(', '{', '['
            stack.push(c)
        when ')'
            return false if stack.pop() != '('
        when '}'
            return false if stack.pop() != '{'
        when ']'
            return false if stack.pop() != '['
        end
    end
    return stack.empty?
end

2. https://leetcode.com/problems/valid-parentheses/discuss/289504/Ruby-Solution
一郎リンクを貼っておくが、MAPPINGのあたりが全然わからない

# @param {String} s
# @return {Boolean}
def is_valid(string)
  stack = []
  
  string.each_char do |char|
    if MAPPING.key?(char)
      stack << MAPPING[char]
    else
      current_open = stack.pop
      return false unless char == current_open
    end
  end
  
  stack.empty?
end

MAPPING = {
  '(' => ')',
  '{' => '}',
  '[' => ']'
}.freeze

この問題から学んだこと

stackという命名はわかりやすい

stackは日本語だと以下の意味になる。LIFO(Last In First Out)方式。
スタックとは何？わかりやすく解説 Weblio辞書

個人的には char_stackというのもありかなと感じた。

わからないこと

以下で取り上げられているMAPPINGというものがわからない
https://leetcode.com/problems/valid-parentheses/discuss/289504/Ruby-Solution

以上