[LeetCode] 1047. Remove All Adjacent Duplicates In String 移除字符串中所有相邻的重复字符
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 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.
这道题给了一个字符串,让移除所有相邻的重复字符,注意之前不相邻的字符可以在其他字符移除后变的相邻,从而形成的新的相邻的重复字符,所以只是简单移除一次不能保证能得到最终的结果。这里需要借助栈的思路来做,可以用字符串来模拟栈的后入先出的特性。遍历每个字符,若 res 不空,且最后一个字符和当前字符相同,则移除掉 res 的最后一个字符,否则将当前字符加入 res 中,这样最后剩下的即为所求,参见代码如下:
解法一:
class Solution {
public:
string removeDuplicates(string S) {
string res;
for (char c : S) {
if (!res.empty() && res.back() == c) {
res.pop_back();
} else {
res.push_back(c);
}
}
return res;
}
};
我们也可以使用双指针来做,两个指针i和j,其中i指向去除重复后的最后一个字符的位置,j为遍历字符串S的位置,首先将 S[j] 赋值给 S[i],然后看若i大于0,且 S[i-1] 和 S[i] 相等的,i自减2,这样就移除了重复,最后根据i的位置取出子串返回即可,参见代码如下:
解法二:
class Solution {
public:
string removeDuplicates(string S) {
int n = S.size(), i = 0;
for (int j = 0; j < n; ++j, ++i) {
S[i] = S[j];
if (i > 0 && S[i - 1] == S[i]) i -= 2;
}
return S.substr(0, i);
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1047
类似题目:
Remove All Adjacent Duplicates in String II
参考资料:
https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/
相关文章
- Leetcode: Integer Replacement
- LeetCode-3.无重复字符的最长子串
- JS leetcode 宝石与石头 题解分析,正则字符组也有妙用
- JS leetcode 移除元素 题解分析
- [LeetCode]1374. 生成每种字符都是奇数个的字符串
- LeetCode 912. 排序数组
- 【数据结构/哈希表】leetcode刷题路线(持续更新)
- leetcode第281场周赛记录
- LeetCode 部分题解 PHP 版
- LeetCode 3. 无重复字符的最长子串
- [LeetCode] 1247. Minimum Swaps to Make Strings Equal 交换字符使得字符串相同
- [LeetCode] 1209. Remove All Adjacent Duplicates in String II 移除字符串中所有相邻的重复字符之二
- [LeetCode] 1171. Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点
- [LeetCode] 1011. Capacity To Ship Packages Within D Days 在D天内送达包裹的能力
- [LeetCode] 838. Push Dominoes 推多米诺骨牌
- [LeetCode] 792. Number of Matching Subsequences 匹配的子序列的个数
- [LeetCode] 1-bit and 2-bit Characters 一位和两位字符
- [LeetCode] 494. Target Sum 目标和
- [LeetCode] Sort Characters By Frequency 根据字符出现频率排序
- [LeetCode] 340. Longest Substring with At Most K Distinct Characters 最多有K个不同字符的最长子串