題目描述

給出一個僅包含字符 '(', ')', '{', '}', '[', ']' 的字符串，判斷該字符串是否是一個合法的括號序列。

• 括號必須以正確的順序關閉。即 "()" 和 "()[]{}" 都是合法的括號序列，而 "(]" 和 "([)]" 是不合法的。

數據范圍：

• 字符串長度 $0\le n\le 10000$

復雜度要求：

• 時間復雜度：$O(n)$
• 空間復雜度：$O(n)$

示例

示例 1:

輸入：

"["

返回值：

false

示例 2:

輸入：

"[]"

返回值：

true

題解

在這道題目中，我們可以使用棧來解決。具體思路如下：

1. 棧的應用：

   • 使用棧來模擬括號的匹配。每次遇到左括號 '(', '{', '[' 時，將其壓入棧中。遇到右括號 ')', '}', ']' 時，判斷棧頂是否是對應的左括號。如果是，則彈出棧頂元素，如果不是，則說明序列不合法。

2. 棧的空檢查：

   • 如果在檢查過程中棧為空且仍然遇到右括號，則說明沒有匹配的左括號，返回 false。

3. 遍歷字符串：

   • 遍歷輸入字符串，如果最后棧為空，則說明所有的括號都正確配對，返回 true。否則，返回 false。

代碼實現

/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可*** @param s string字符串* @return bool布爾型*/
#define MAX_SIZE 10000  // 假設棧最大容量// 用一個棧存儲括號
char stack[MAX_SIZE];
int top = -1; // 棧頂指針，初始化時棧為空// 將字符s1壓入棧
void push(char s1) {stack[++top] = s1;
}// 從棧中彈出一個字符
char pop() {return stack[top--];
}// 判斷棧是否為空
bool isEmpty() {return top == -1;
}// 判斷字符串是否是有效的括號序列
bool isValid(char* s) {// 遍歷字符串中的每個字符for (int i = 0; s[i] != '\0'; i++) {// 如果棧為空且當前字符是右括號，則返回falseif (isEmpty()) {if (s[i] == '}' || s[i] == ']' || s[i] == ')') {return false;} else {push(s[i]); // 否則將當前左括號壓入棧}} else { // 如果棧非空并且當前字符是右括號if (s[i] == '}' || s[i] == ']' || s[i] == ')') {char temp = pop(); // 彈出棧頂元素// 檢查棧頂元素是否與當前右括號匹配if ((s[i] == '}' && temp != '{') || (s[i] == ']' && temp != '[') || (s[i] == ')' && temp != '(')) {return false; // 不匹配則返回false}} else {push(s[i]); // 否則將當前左括號壓入棧}}}// 遍歷完字符串后，棧應該為空return isEmpty();
}

代碼解析

1. 定義棧和棧操作

#define MAX_SIZE 10000  // 假設棧最大容量
char stack[MAX_SIZE];  // 用于存儲括號
int top = -1; // 棧頂指針，初始化時棧為空

• 定義了一個大小為 MAX_SIZE 的棧數組 stack，用于存儲括號。
• 棧頂指針 top 初始化為 -1，表示棧為空。

2. 棧的基本操作

• push: 將一個字符壓入棧。

void push(char s1) {stack[++top] = s1;  // 將字符壓入棧
}

• pop: 從棧中彈出一個字符。

char pop() {return stack[top--];  // 返回棧頂元素并將棧頂指針下移
}

• isEmpty: 判斷棧是否為空。

bool isEmpty() {return top == -1;  // 如果棧頂指針為-1，表示棧為空
}

3. 主函數 isValid

isValid 函數遍歷字符串，對于每個字符，判斷是左括號還是右括號，并進行相應的棧操作：

• 左括號處理: 遇到左括號時直接壓入棧。
• 右括號處理: 遇到右括號時，彈出棧頂元素并進行匹配。如果匹配失敗，則返回 false。
• 邊界條件: 在遍歷完成后，如果棧為空，則說明括號序列合法，否則不合法。

4. 返回值

• 如果棧為空，說明所有括號都匹配，返回 true；否則返回 false。

時間和空間復雜度分析

• 時間復雜度: 每個字符僅遍歷一次，棧操作（壓棧和彈棧）都是常數時間操作，因此總的時間復雜度是 $O(n)$，其中 $n$ 是字符串的長度。

• 空間復雜度: 由于需要使用一個棧來存儲括號，棧的最大容量為字符串長度 $n$，因此空間復雜度是 $O(n)$。