資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中最小刪除以使括號有效
假設我們有一個包含 '('、')' 和小寫英文字母的字串 s。我們必須刪除最少數量的括號（ '(' 或 ')'，位於任何位置），以便生成的括號字串有效，並返回任何有效的字串。當滿足所有這些條件時，括號字串才有效：
它是空字串，僅包含小寫字元，或者
它可以寫成 AB 的形式（A 與 B 連線），其中 A 和 B 是有效的字串，或者
它可以寫成 (A) 的形式，其中 A 是有效的字串。
因此，如果輸入類似於“a)b(c)d”，則輸出將是“ab(c)d”。
為了解決這個問題，我們將遵循以下步驟：
定義一個棧 st
對於 i 從 0 到 s 的大小
如果 s[i] = ‘(’，則將 i 插入 st
否則，當 s[i] 為 ‘)’ 時，
如果棧不為空，則從棧中彈出，否則 s[i] = ‘*’
當 st 不為空時，
s[棧頂元素] = ‘*’
從棧中彈出
ans := 空字串
對於 i 從 0 到 s 的大小 - 1
如果 s[i] 不為 ‘*’，則 ans := ans + s[i]
返回 ans
讓我們看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minRemoveToMakeValid(string s) {
stack <int> st;
for(int i = 0; i < s.size(); i++){
if(s[i] == '(')st.push(i);
else if(s[i] == ')'){
if(!st.empty())st.pop();
else s[i] = '*';
}
}
while(!st.empty()){
s[st.top()] = '*';
st.pop();
}
string ans = "";
for(int i = 0; i < s.size(); i++){
if(s[i] != '*')ans += s[i];
}
return ans;
}
};
main(){
Solution ob;
cout << (ob.minRemoveToMakeValid("a)b(c)d"));
}輸入
"a)b(c)d"
輸出
ab(c)d
更新於：2020年5月2日
383 次檢視
廣告