退格键消除-栈

退格键消除问题-栈

题目描述

代码语言：javascript复制

输入一个字符串只包含$和小写英文字母的字符串s，如ab$$cd，每遇到一个字符$，就删除其前面的字符（如果有的话）；最后输出的字符串中不包含$字符，求最后返回剩余的小写英文字符的总长度。
示例1：
 输入：a$b$cd
输出：2
说明：a$b$cd -> b$cd -> cd 
剩余字符串长度为2

示例2：
输入：$ab$c$$$d$$$
输出：0
说明：$ab$c$$$d$$$ -> $ac$$$d$$$ -> $a$$d$$$ -> $$d$$$ -> $$$$ -> 空字符串，
剩余字符串长度为0

解题思路 数据结构-栈

这道题很容易联想到栈的特性：先进后出， 遍历输入字符串，遇到不是的字符，则入栈；遇到字符，若当前栈不为空，则将栈顶元素弹出。 直至遍历结束，最终栈中的元素个数就是所求的剩余的小写英文字符的总长度

C 代码实现

代码语言：javascript复制

#include <iostream>
#include <string>
#include <stack>
using namespace std;

class Solution
{
public:
	// 借用栈先进后出的特性做消除
	int GetBackSpaceCnt(const std::string& inputStr)
	{
		int res = 0;
		stack<char> myStack;
		// 遍历输入字符串
		for (int i = 0; i < inputStr.size(); i  ) {
			char ch = inputStr[i];
			if (ch != '$') {
				// 若当前元素不为$，是英文字母，则入栈
				myStack.push(ch);
			} else {
				// 若当前元素是$，且栈非空，则将栈顶元素弹出
				if (!myStack.empty()) {
					myStack.pop();
				}
			}
		}
		// 返回栈中元素个数
		return myStack.size();
	}
};

inline std::string ReadLine()
{
	string line;
	getline(cin, line);
	return line;
}

int main()
{
	std::string inputStr = ReadLine();
	Solution solu;
	std::cout << solu.GetBackSpaceCnt(inputStr);

	return 0;
}

数据结构 std string 遍历 字符串

0 人点赞