20 - Valid parenthesis

[AlphabetsAlphabets]

Discussion about the solution to this question. Didn't know how to do this at all. Solution from neetcode

pub fn is_valid(s: String) -> bool {
    let mut stack: Vec<char> = vec![];
    let mut matching_paren: HashMap<char, char> = HashMap::new();
    matching_paren.insert(')', '(');
    matching_paren.insert(']', '[');
    matching_paren.insert('}', '{');

    for c in s.chars() {
        if matching_paren.contains_key(&c) {
            let last = stack[stack.len() - 1];
            let paren = matching_paren.get(&c).unwrap();

            if !stack.is_empty() && last == *paren {
                stack.pop();
            } else {
                return false;
            }
        } else {
            stack.push(c);
        }
    }

    if stack.is_empty() {
        true
    } else {
        false
    }

This is the solution suggested by neetcode and it works. The discussion is to find out why it works.

[AlphabetsAlphabets]

The part that has me stumped is this part.

let last = stack[stack.len() - 1];
let paren = matching_paren.get(&c).unwrap();

if .. && last == *paren {

Why is last == *paren even a working solution? I decided to come up with a quick test.

pub fn main() {
    let parens = "[()]".to_string();
    let result = is_valid(parens.clone());
    println!("Is '{}' valid? {}", parens, result);
}

In the third iteration where c = ), last = ( and paren = (. It was quite straight forward after some debugging. If the current character is an closing bracket ), ] or } then the top most item in the stack must be the accompanying closing bracket for it to be a pair of valid parethesis. Getting the value behind the key c is to ensure that the previous character is the correct closing bracket. If it is the incorrect closing bracket it is invalid parethesis and false can be safetly returned.

As for the first two iterations it gets to stack.push(c). Reason being if it is an open bracket it still needs to be closed no reason to return anything prematurely. As long as the inner brackets gets closed properly as well.

The final if at the bottom checks if the stack is empty and returns true if it is. That's because if the parenthesis are valid stack.pop is called meaning if stack is empty then everything is alright.