一, 题目
给出由小写字母组成的字符串 S, 重复项删除操作会选择两个相邻且相同的字母, 并删除它们.
在 S 上反复执行重复项删除操作, 直到无法继续删除.
在完成所有重复项删除操作后返回最终的字符串. 答案保证唯一.
示例:
输入:"abbaca"
输出:"ca"
解释:
例如, 在 "abbaca" 中, 我们可以删除 "bb" 由于两字母相邻且相同, 这是此时唯一可以执行删除操作的重复项.
之后我们得到字符串 "aaca", 其中又只有 "aa" 可以执行重复项删除操作, 所以最后的字符串为 "ca".
提示:
1 <= S.length <= 20000
S 仅由小写英文字母组成.
二, 题解
题解 1:PHP 自带的函数 str_replace
将 aa 到 zz 的 26 种重复项放入集合中, 将字符串中这些重复项替换成空字符串.
- function removeDuplicates($S) {
- $vowels = ['aa', 'bb', 'cc', 'dd', 'ee', 'ff', 'gg', 'hh', 'ii', 'jj', 'kk', 'll', 'mm', 'nn',
- 'oo', 'pp', 'qq', 'rr', 'ss', 'tt', 'uu', 'vv', 'ww', 'xx', 'yy', 'zz'];
- while (strlen($S)>= 2) {
- $S = str_replace($vowels, "", $S);
- if ($S == str_replace($vowels, "", $S)) {
- break;
- }
- }
- return $S;
- }
题解 2: 出队入栈结合
首先把字符串转化为数组, 可以把这个字符串数组当做一个队列;
设置一个栈, 判断字符串数组的队头元素和栈顶元素是否相等, 如果不相等, 就将字符串数组的队首元素出队, 压入栈中,
反之, 则将队首元素出队, 同时将栈顶元素弹出.
时间复杂度: O(N), 空间复杂度: O(N).
- function removeDuplicates($S) {
- if (strlen($S) <= 1) {
- return $S;
- }
- $stack = [];
- $arr = str_split($S);
- while (!empty($arr)) {
- if (empty($stack)) {
- $stack[] = array_shift($arr);
- } else {
- if (current($arr) == end($stack)) {
- array_shift($arr);
- array_pop($stack);
- } else {
- $stack[] = array_shift($arr);
- }
- }
- }
- return implode("", $stack);
- }
来源: https://www.cnblogs.com/sunshineliulu/p/12634719.html