您的位置 首页 > 数码极客

括号在字符串中如何存储

文 | 猿天罡

本题源自LeetCode[1],题号20。

1.题目描述

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()" 输出: true

示例 2:

输入: "()[]{}" 输出: true

示例 3:

输入: "(]" 输出: false

示例 4:

输入: "([)]" 输出: false

示例 5:

输入: "{[]}" 输出: true

2.解题思路

题目的意思是:给定一串括号组成的字符串,让我们判断括号闭合顺序和类型是否正确。

从示例中也可以明白题意。

我们可以用栈结构来解决这道题。栈是先进后出的一种数据结构。如果我们把一些数字顺序存进栈结构中,那么我们取出数字的顺序是和存储顺序相反的。

为了更好地理解栈这种结构,我简单地画了张图。


我们把数字1,2,3,4依次存储到栈的过程称作进栈/压栈,把4,3,2,1依次取出的过程称作出栈/弹栈。

算法具体过程:

  1. 初始化栈S。
  2. 一次处理给定字符串中的每一个括号。
  3. 如果遇到开括号,我们就将其压栈。
  4. 如果遇到闭括号,我们就检查栈顶元素(即上图所示栈中最上面的元素)。
  5. 如果栈顶元素是一个相同类型的左括号,那么我们将把它从栈中弹出来并继续处理。
  6. 否则,这表示给定字符串无效。
  7. 如果到最后栈中还剩下元素,也表示给定字符串无效

3.算法动画

假设给定的字符串是{[()]},依照上面的算法,运行过程如下。

有效的括号

如果给定的字符串是{[(]]},依照上面的算法,运行过程如下。

无效的括号

4.代码实现

由于个人精力有限,暂时只提供Java语言代码实现。只要理解了本算法的思想,你也能用其他语言实现出来,这也是对个人代码能力的锻炼。

class Solution { private Map<Character, Character> map; public Solution() { = new HashMap<Character, Character>(); .put(')', '('); .put(']', '['); .put('}', '{'); } public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (.containsKey(c)) { // 是闭括号 char topElement = () ? '#' : (); if (topElement != .get(c)) // 括号不匹配 return false; } else { // 开括号 (c); } } return (); } }

5.结语

说到令我们计算机专业最头疼的学科是啥,我猜十有八九会有人投「数据结构」一票,有的算法代码虽然十分简短,可是学起来真的会让人头秃。

除了怀着对计算机行业前辈们的无限憧憬以外,对算法我们其实是敬畏的。

我想,如果能用动画的方式去展示算法运行的过程却是极好的。这样不管是学习还是面试只要脑海中记住动画,心中大体就有了思路。

如果这篇文章对您有所帮助,欢迎点赞、转发加收藏啦~

或者您有任何疑问,可以随时与我联系,感谢您的阅读,我们下期再见。

▼往期精彩回顾 ▼

图解算法:两数之和

图解算法第二弹:整数反转

图解算法第三弹:回文数


责任编辑: 鲁达

1.内容基于多重复合算法人工智能语言模型创作,旨在以深度学习研究为目的传播信息知识,内容观点与本网站无关,反馈举报请
2.仅供读者参考,本网站未对该内容进行证实,对其原创性、真实性、完整性、及时性不作任何保证;
3.本站属于非营利性站点无毒无广告,请读者放心使用!

“括号在字符串中如何存储”边界阅读