###### tags: `leetcode` `rust`

# 対応するカッコ

- https://leetcode.com/problems/valid-parentheses/

開きカッコと閉じカッコが対応しているかどうかを調べるプログラムを Rust で書く。

### 問題
文字列 s のカッコが開きカッコと閉じカッコで正しく対応できていれば true を、そうでなければ false を返すプログラムを作成する。
文字列 s に入る文字は、'(', ')', '[', ']', '{', '}' のみ。

s = "()"      // -> true
s = "()[]{}"  // -> true
s = "(]"      // -> false

## 初期コード

is_valid 関数を完成させる。

impl Solution {
    pub fn is_valid(s: String) -> bool {
    }
}

## bytes と chars
String 型の s から 1 文字ずつ取り出す際に使用できるメソッドに bytes と chars がある。
- [bytes](https://doc.rust-lang.org/std/string/struct.String.html#method.bytes)
- [chars](https://doc.rust-lang.org/std/string/struct.String.html#method.chars)

bytes と chars の違いは、bytes は 1 バイトの取得になるが、chars は 1 文字の取得になるので 2 バイト文字の場合は 2 バイトの 1 文字を取得する。
そのため chars の方が bytes より少し遅い。

## struct Vec
ドキュメント
- [Vec](https://doc.rust-lang.org/std/vec/struct.Vec.html)

vec は push / pop メソッドを使用すればスタックのように使える。

vec の pop メソッドは Option<T> 型を返却する。
値が入っていない場合は None を、入っている場合は Some(x) が返却される。
- [pop](https://doc.rust-lang.org/std/vec/struct.Vec.html#method.pop)

## if let Some
Option<T> 型が返却される場合に、`if let Some(x) = vec.last()` を使うことで、Some が返却された場合にのみ処理を行うという記述ができるイディオム。None の場合は何もしない。
例

if let Some(l) = stack.last() {
    if *l == b {
        ...
    }    
}

## b'('
文字の前に b を付けることで byte を表現している。0x10 の 0x のようなもの。

## アルゴリズム
- 文字列 s を 1 バイトずつ読み込む。
- 読み込んだ文字が開きカッコならば、対応する閉じカッコを ベクター vec に登録する。
- 開きカッコ以外ならば、vec の内容に応じて処理を行う。
- vec が空ならば false を返却する（開きカッコがないのに閉じようとしている）。
- vec の最後に登録されている要素（vec.last()）が読み込んだ文字と同じならば対応する閉じカッコなので vec の最後から要素を取り出す（vec.pop()）、それ以外の場合は false を返却する（開きカッコに対応する閉じカッコでなかった）。
- for ループ終了後に vec が空になっていれば true を返却する（vec が空になっていない場合は、閉じカッコが足りていないので false）。

## 完成したコード

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut vec = Vec::new(); 
        for b in s.bytes() {
            //println!("{}", b);
            
            match b {
                b'(' => vec.push(b')'),
                b'{' => vec.push(b'}'),
                b'[' => vec.push(b']'),
                _ => { 
                    // None or Some(b'(')
                    if let Some(&l) = vec.last() {
                        if l == b {
                            vec.pop();
                            continue;
                        }
                    }
                    return false;
    
                    // 苦戦の名残（これも動く）
                    /* 
                    //println!("{:?}", vec.last());
                    if vec.is_empty() == true {
                        return false;
                    }
                    
                    //let p = vec.last().unwrap();
                    //println!("-- {:?},{:?}", p, b);
                    //if p == &b {
                    if vec.last().unwrap() == &b {
                        vec.pop();
                    } else {
                        return false;
                    }
                    */
                }
            }
        }
        //println!("++ {:?}", vec);
        vec.len() == 0
    }
}