22. 括号生成

每天一道Rust-LeetCode(2020-02-14)

坚持每天一道题,刷题学习Rust.

题目描述

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解题思路

用left:表示剩下的左括号个数
用right表示剩下的右括号个数
碰到left==right,只能消耗左括号,否则可以尝试左右
left是不可能大于right的,这种情况肯定不会出现匹配的结果
直到最终消耗完毕

解题过程

struct Solution {}

impl Solution {
    fn generate_internal(left: i32, right: i32, cur: &Vec<u8>, res: &mut Vec<String>) {
        if left == right && left == 0 {
            res.push(unsafe { String::from_utf8_unchecked(cur.clone()) });
            return;
        }
        if left < 0 || right < 0 {
            panic!("impossible")
        }
        if left > 0 {
            let mut cur = cur.clone();
            cur.push('(' as u8);
            Self::generate_internal(left - 1, right, &cur, res);
        }
        //left最多和right相等还是一个正确的状态,如果left>right,说明出错了.
        if left < right {
            let mut cur = cur.clone();
            cur.push(')' as u8);
            Self::generate_internal(left, right - 1, &cur, res);
        }
    }
    pub fn generate_parenthesis(n: i32) -> Vec<String> {
        let mut left = n;
        let mut right = n;
        let mut res = Vec::new();
        let mut cur = Vec::new();
        Self::generate_internal(left, right, &cur, &mut res);
        res
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn it_works() {
        let t = Solution::generate_parenthesis(1);
        println!("t={:?}", t);
        let t = Solution::generate_parenthesis(2);
        println!("t={:?}", t);
        let t = Solution::generate_parenthesis(3);
        println!("t={:?}", t);
    }
}

一点感悟

其他

欢迎关注我的github,本项目文章所有代码都可以找到.