LeetCode 20. Valid Parentheses (LaTeX)

15 Jun 2020

Example
Notes
Solution
Output

Given a string 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

Example 1:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Notes

An empty string is also considered valid.

Solution

\documentclass{article}
\usepackage[a3paper, landscape]{geometry}
\usepackage{newtxtext, newtxmath}
\usepackage{amsmath}
\usepackage{datetime2}
\usepackage{expl3}

\begin{document}

\ExplSyntaxOn

\str_new:N \l_tmpc_str

\prop_new:N \g_paren_prop
\prop_gput:Nnn \g_paren_prop {[} {]}
\prop_gput:Nnn \g_paren_prop {(} {)}
\prop_gput:NVV \g_paren_prop {\c_left_brace_str} {\c_right_brace_str}

\par\cs_meaning:N \g_paren_prop

\tl_new:N \g_result_tl

\cs_new:Npn \is_paren_valid:n #1 {
    \seq_gclear:N \g_tmpa_seq
    \str_gset:Nn \g_tmpa_str {#1}
    \exp_args:NNV \str_gremove_all:Nn \g_tmpa_str {\space}
    
    \par processed~input:~\str_use:N \g_tmpa_str
    \str_map_variable:NNn \g_tmpa_str \l_tmpa_str {
        \prop_if_in:NVTF \g_paren_prop \l_tmpa_str {
            % left parenthesis encountered
            \seq_gput_left:NV \g_tmpa_seq \l_tmpa_str
        } {
            % right parenthesis encountered
            \seq_get_left:NNTF \g_tmpa_seq \l_tmpb_str {
                % \l_tmpb_str is the head (last left parenthesis)
                % get corresponding right string from prop list
                \prop_get:NVN \g_paren_prop \l_tmpb_str \l_tmpc_str
                \str_if_eq:VVTF \l_tmpa_str \l_tmpc_str {
                    \seq_gpop_left:NN \g_tmpa_seq \l_tmpa_tl
                } {
                    % if parenthesis mismatch, return false
                    \tl_gset:Nn \g_result_tl {false}
                    \str_map_break:
                }
            } {
                % if the sequence is empty, return false
                \tl_gset:Nn \g_result_tl {false}
                \str_map_break:
            }
        }
    }
    \seq_if_empty:NTF \g_tmpa_seq {
        \tl_gset:Nn \g_result_tl {true}
    }{
        \tl_gset:Nn \g_result_tl {false}
    }
}

\cs_generate_variant:Nn \is_paren_valid:n {x}

\is_paren_valid:x {\c_left_brace_str  [ (()) ] \c_right_brace_str}
\par \textbf{result:~\tl_use:N \g_result_tl}
\is_paren_valid:x {(}
\par \textbf{result:~\tl_use:N \g_result_tl}
\is_paren_valid:x {[[((()))]]}
\par \textbf{result:~\tl_use:N \g_result_tl}
\is_paren_valid:x {([)]}
\par \textbf{result:~\tl_use:N \g_result_tl}

\ExplSyntaxOff

\par\DTMNow

\end{document}

Output

macro:->\s__prop \__prop_pair:wn [\s__prop {]}\__prop_pair:wn (\s__prop {)}\__prop_pair:wn {\s__prop {}}
processed input: {[(())]}
result: true
processed input: (
result: false
processed input: [[((()))]]
result: true
processed input: ([)]
result: false
2020-06-15 12:43:28-04:00

Alan Xiang's Blog

LeetCode 20. Valid Parentheses (LaTeX)

Example

Notes

Solution

Output