1. 题⽬链接:844.⽐较含退格的字符串
2. 题⽬描述:
3. 解法(⽤数组模拟栈):
算法思路:
由于退格的时候需要知道「前⾯元素」的信息,⽽且退格也符合「后进先出」的特性。因此我们可以 使⽤「栈」结构来模拟退格的过程。
• 当遇到⾮# 字符的时候,直接进栈;
• 当遇到# 的时候,栈顶元素出栈。
为了⽅便统计结果,我们使⽤「数组」来模拟实现栈结构。
C++算法代码:
class Solution
{
public:
//处理字符串
string changestr(string key)
{
string a;
for(int i=0;i<key.size();i++)
{
if(key[i]!='#')
{
a+=key[i];
}
else
{
if(a.size())
{
a.pop_back();
}
}
}
return a;
}
bool backspaceCompare(string s, string t)
{
return changestr(s)==changestr(t);
}
};
Java算法代码:
class Solution
{
public boolean backspaceCompare(String s, String t)
{
return changeStr(s).equals(changeStr(t));
}
public String changeStr(String s)
{
StringBuffer ret = new StringBuffer(); // ⽤数组模拟栈结构
for (int i = 0; i < s.length(); i++)
{
char ch = s.charAt(i);
if (ch != '#')
{
ret.append(ch); // ⼊栈
}
else
{
if (ret.length() > 0) ret.deleteCharAt(ret.length() - 1); // 出栈
}
}
return ret.toString();
}
}
标签:String,ret,算法,退格,字符串,public,模拟,string
From: https://blog.csdn.net/2301_79580018/article/details/141687802