これは何

Rustにもっと慣れたい初心者が泣きながらLeetcodeの問題をRustで解いて、その過程を晒します。
初心者🔰なので暖かい目で見守っていただけると幸いです。

skitzville

今日の問題

skitzville

以前TS使って解いた時の回答

sにループ処理をかける形で作成。

opening bracketが出てきた際に対となるclosing bracketをheapに保存。
closing bracketの場合はheapの最後の値と一致しているかをチェック
1. 一致していればheapの最後の要素を削除
2. 一致しなければfalseをreturn

type ClosingBracket = typeof table[keyof typeof table];
const table = {
    "[": "]",
    "{": "}",
    "(": ")"
} as const;

function isValid(s: string): boolean {
    let heap: ClosingBracket[] = [];
    for (let i = 0; i < s.length; i++) {
        const curr = s[i];
        // handle opening bracket
        if (table[curr]) {
            heap.push(table[curr]);
        } else {
            // handle closing bracket
            const lastElm = heap[heap.length - 1];
            if (lastElm === curr) {
                heap.pop();
            } else {
                return false;
            }
        }
    }
    if (heap.length > 0) return false;
    return true;
};

skitzville

Rustで解いてみる

まずはTypeScriptで作成した時と同じ方法で実装する方向で進めてみた。（ものすごい長くなってしまったけど、とりあえずSubmissionしたところパスした）

use std::collections::HashMap;

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut brackets = HashMap::new();
        brackets.insert('{', '}');
        brackets.insert('[', ']');
        brackets.insert('(', ')');

        let mut heap = Vec::new();

        for elm in s.chars() {
            match brackets.get(&elm) {
                // handle opening bracket
                Some(c) => {
                   heap.push(c);
                }
                // handle closing bracket
                None => {
                    match heap.get(heap.len() - 1) {
                        None => {
                            return false;
                        }
                        Some(t) => {
                            if elm == **t {
                                heap.pop();
                            } else {
                                return false;
                            }
                        }
                    }
                }
            }
        }

        if heap.len() > 0 {
            return false;
        }
        
        return true;
    }
}

skitzville

実装中のあれこれ

以下実際に解いてる時に考えていたことや苦戦したポイントなど

charsを使うのが一番手軽で良さそう

getでHashMapの中からkey指定で要素を取得する
- docにもあるようにreferenceをパラメータで渡してあげる必要がありそう
- 対象の要素が存在しない場合もあるのでOptionが返ってくる

getでVectorの中からindex指定で要素を取得する
- TS同様[]でも指定ができるけど、存在しないindexを指定してしまった場合クラッシュしてしまうためgetを使用
- 対象の要素が存在しない場合もあるのでOptionが返ってくる

skitzville

その他

やたら長いのでもっといい解き方あるだろと思いChatGPTにお願いしてみた。
格段にシンプルで分かりやすいコードになってて泣きそうになる。

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut stack: Vec<char> = Vec::new();
        for c in s.chars() {
            if c == '(' || c == '{' || c == '[' {
                stack.push(c);
            } else {
                if stack.is_empty() {
                    return false;
                }
                let top = stack.pop().unwrap();
                if (c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[') {
                    return false;
                }
            }
        }
        stack.is_empty()
    }
}

skitzville

今日も何とか泣かずに乗り切れました。

このスクラップは2023/05/22にクローズされました