一、题目描述

游戏规则：输入一个只包含英文字母的字符串，字符串中的两个字母如果相邻且相同，就可以消除。

在字符串上反复执行消除的动作，直到无法继续消除为止，此时游戏结束。

请输出最终得到的字符串长度。

1.1 输入描述

输入原始字符串 str，只能包含大小写因为字母，字母大小写敏感，str 长度不超过 100。

1.2 输出描述

输出游戏结束后，最终得到的字符串长度。

1.3 测试样例

1.3.1 示例 1

输入

gg

输出

说明

gg 可以直接消除，得到空串，长度为 0。

1.3.2 示例 2

输入

mMbccbc

输出

说明：在 mMbccbc 中，可以先消除 cc，得到 mMbbc；再消除 bb，得到 mMc。此时无法再消除，最终长度为3

备注：输入中包含非大小写英文字母时，均为异常输入，直接返回 0。

二、解题思路

本文实际考查的是「双向链表」的删除。算法步骤如下所示：

（1）首先，将字符串转化为双向链表存储；

（2）然后遍历字符串，如果当前字符和前一个字符相同，则删除这两个字符，删除后重新连接双向链表；

（3）继续处理下一个元素，直到处理到最后一个元素。

三、代码实现

代码实现如下所示。

#include <iostream>
#include <list>
using namespace std;struct Node {char value;struct Node* pre;struct Node* next;Node():value(' '),pre(nullptr),next(nullptr){}Node(char val):value(val),pre(nullptr),next(nullptr){}
};int main()
{string str;while (cin>>str) {int n = str.size();Node* head = new Node;Node* pre = head;for (int i = 0; i < n; ++i) {Node* tmp = new Node(str[i]);tmp->pre = pre;pre->next = tmp;pre = tmp;}Node* p = head->next;while (p) {if (p->pre->value == p->value) {p->pre->pre->next = p->next;if (p->next) {p->next->pre = p->pre->pre;} else {break;}}p = p->next;}p = head->next;int num = 0;while (p) {num++;p = p->next;}cout<<num<<endl;}return 0;
}