，判断字符串是否有效。输入的字符串在长度上最长可能达到10000，其中只包含「(」「)」「{」「}」「[」「]」六种字符。

在日常的编程中，我们经常会遇到需要判断字符串有效性的问题，尤其是在处理一些数据结构的实现时，比如栈、队列等。而对于一个只包含「(」「)」「{」「}」「[」「]」的字符串，如何判断其是否有效呢？

我们可以借助栈的思想来解决这个问题。具体来说，我们从字符串的左侧开始遍历，将遇到的左括号按顺序入栈。当遇到右括号时，我们检查栈顶元素是否与该右括号匹配，若匹配，则弹出栈顶元素；否则，返回false。

以下是具体实现过程：

bool isValid(string s) {
  stack<char> st;
  for (char c : s) {
    if (c == '(' || c == '{' || c == '[') {
      st.push(c);
    } else if (c == ')' || c == '}' || c == ']') {
      if (st.empty())
        return false;
      
      char t = st.top();
      st.pop();
      if ((c == ')' && t != '(') ||
        (c == '}' && t != '{') ||
        (c == ']' && t != '['))
        return false;
      
    }
  }
  return st.empty();
}

其中，stack是STL中的栈容器，st.top()返回栈顶元素，st.pop()弹出栈顶元素。

时间复杂度为O(n)，空间复杂度为O(n)。

相似文章
• C++实现栈数据结构进行进制转换
  在计算机科学中，栈是一种常见的数据结构，它遵循先进后出的原则。栈可以被用于处理众多计算机科学问题，包括算术表达式求解、逆波兰表达式、编译器实现、以及操作系统的内存管理等。
  
  
• C++中如何使用栈数据结构
  栈是一种常用的数据结构，在C++语言中也有相应的实现。栈可以理解为“一摞书”，我们向这一摞书中加入元素时，只能往最上面加。同理，我们从这一摞书中取出元素时，也只能取出最上面的那个。栈的操作通常包括入栈（push）和出栈（pop）。
  
  
• C++实现栈：入栈和出栈
  C++是一种流行的编程语言，广泛用于许多应用程序的构建中。在这些应用程序中，栈是常见的数据结构之一，C++中也提供了栈的数据类型。本文将介绍如何使用C++实现栈的入栈和出栈操作。
  
  
• C++ 栈： 实现与操作
  C++
  
  
• C++语言栈介绍与应用
  C++语言是一种功能丰富的编程语言，具有广泛的应用，尤其是在开发计算机程序时。其中栈也是C++语言中的一项常用数据结构。本篇文章将介绍C++语言栈的基本概念和应用。
  
  
• Java实现计算器程序：代码案例分享
  Java实现计算器程序：代码案例分享
  
  
• Java实现最大括号深度：从基础到实践
  Java实现最大括号深度：从基础到实践
  
  
• Java计算器程序代码思路详解
  Java计算器程序代码思路详解
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政