(栈,双端队列,双指针) leetcode. 844 Backspace String Compare
思路一:定义两个栈(肯定不是O(1)的空间复杂度)
class Solution { public: bool backspaceCompare(string S, string T) { //栈 stack<char> s, t; for(char a : S){ if(a == '#'){ if(s.empty()) continue; else s.pop(); } else s.push(a); } for(char a : T){ if(a == '#'){ if(t.empty()) continue; else t.pop(); } else t.push(a); } if(s.size()!= t.size()) return false; for(int i=0; i<s.size(); ++i){ if(s.top() != t.top()) return false; else{ s.pop(); t.pop(); } } return true; } };
思路二:双端队列:
deque(双端队列)是一种具有队列和栈的性质的数据结构。双端队列的元素可以从两端弹出,其限定插入和删除操作在表的两端进
#include <deque>
deque<int>s1; deque<string>s2;
//a) 构造函数 deque<int> ideq //b)增加函数 ideq.push_front( x):双端队列头部增加一个元素X ideq.push_back(x):双端队列尾部增加一个元素x //c)删除函数 ideq.pop_front():删除双端队列中最前一个元素 ideq.pop_back():删除双端队列中最后一个元素 ideq.clear():清空双端队列中元素 //d)判断函数 ideq.empty() :向量是否为空,若true,则向量中无元素 //e)大小函数 ideq.size():返回向量中元素的个数
class Solution { public: bool backspaceCompare(string S, string T) { return edit(S) == edit(T); } string edit(string& s){ deque<char> dq; for(auto c : s){ if(c == '#'){ if(!dq.empty()) dq.pop_back(); } else dq.push_back(c); } return string(dq.begin(), dq.end()); } };
将一个char类型的数组转换为一个string类型字符:
#include <iostream> int main() { char arr[] = "Techie Delight"; std::string s(arr); std::cout << s; return 0; }
#include <iostream> int main() { char arr[] = "Techie Delight"; std::string s = arr; std::cout << s; return 0; }
思路三:双指针:设置两个指针 s_p 和 t_p 分别指向S和T的末尾位置;再设置s_k 和 t_k 表示S和T中#的个数。
注意判断边界条件。
class Solution { public: bool backspaceCompare(string S, string T) { int s_p = S.size()-1, t_p = T.size()-1; int s_k = 0, t_k = 0; while(s_p >= 0 || s_p>=0){ while(s_p >=0 ){ if(S[s_p] == '#'){ s_k ++; s_p --; } else if(s_k > 0){ s_p --; s_k--; } else break; } while(t_p >=0 ){ if(T[t_p] == '#'){ t_k ++; t_p --; } else if(t_k > 0){ t_p --; t_k --; } else break; } if( (s_p>=0) != (t_p>=0) ) return false; if( (s_p >=0) && (t_p >=0) && (S[s_p] != T[t_p]) ) return false; s_p --; t_p --; } return true; } };