1047 Remove All Adjacent Duplicates In String 刪除字符串中的所有相鄰重復項
Description:
Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.
We repeatedly make duplicate removals on S until we no longer can.
Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.
Example:
Example 1:
Input: "abbaca"
Output: "ca"
Explanation:
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".
Note:
1 <= S.length <= 20000
S consists only of English lowercase letters.
題目描述:
給出由小寫字母組成的字符串 S笆载，重復項刪除操作會選擇兩個相鄰且相同的字母，并刪除它們涯呻。
在 S 上反復執(zhí)行重復項刪除操作凉驻，直到無法繼續(xù)刪除。
在完成所有重復項刪除操作后返回最終的字符串复罐。答案保證唯一涝登。
示例 :
輸入："abbaca"
輸出："ca"
解釋：
例如，在 "abbaca" 中效诅，我們可以刪除 "bb" 由于兩字母相鄰且相同胀滚，這是此時唯一可以執(zhí)行刪除操作的重復項。之后我們得到字符串 "aaca"乱投，其中又只有 "aa" 可以執(zhí)行重復項刪除操作咽笼，所以最后的字符串為 "ca"。
提示：
1 <= S.length <= 20000
S 僅由小寫英文字母組成戚炫。
思路:
參考LeetCode #20 Valid Parentheses 有效的括號
將字符壓入棧, 再比較, 相同的丟棄
時間復雜度O(n), 空間復雜度O(1)
代碼:
C++:
class Solution
{
public:
string removeDuplicates(string S)
{
int top = 0;
for (auto c : S)
{
if (!top or S[top - 1] != c) S[top++] = c;
else top--;
}
S.resize(top);
return S;
}
};
Java:
class Solution {
public String removeDuplicates(String S) {
StringBuilder result = new StringBuilder();
for (int i = 0; i < S.length(); ++i) {
if (result.length() == 0) result.append(S.charAt(i));
else if (result.charAt(result.length() - 1) == S.charAt(i)) result.setLength(result.length() - 1);
else result.append(S.charAt(i));
}
return result.toString();
}
}
Python:
class Solution:
def removeDuplicates(self, S: str) -> str:
s = []
for c in S:
if s and s[-1] == c:
s.pop()
else:
s.append(c)
return ''.join(s)
