844. Compare strings with backspace
Link to force buckle topic: https://leetcode-cn.com/problems/backspace-string-compare
Given two strings S and T, when they are input into a blank text editor respectively, judge whether they are equal and return the result# Represents a backspace character.
Note: if you enter a backspace character for empty text, the text continues to be empty.
Example 1:
- Input: S = "ab#c", T = "ad#c"
- Output: true
- Explanation: both S and T will become "ac".
Example 2:
- Input: S = "ab##", T = "c#d#"
- Output: true
- Explanation: both S and T will become "".
Example 3:
- Input: S = "a##c", t = "a#a#c"
- Output: true
- Explanation: both S and T will become "c".
Example 4:
- Input: S = "a#c", T = "b"
- Output: false
- Explanation: S will become "c", but T is still "b".
thinking
This paper will give a stack simulation method with spatial complexity O(n) and a double pointer method with spatial complexity O(1).
Common method (idea of using stack)
This topic is to use the rhythm of the stack. This matching (elimination) problem is also what the stack is good at. The students who brush the questions together should know that Stack and queue: matching is the strength of stack , I've already mentioned using the stack to do similar things once.
Well, the idea of stack can be used for this problem, but it is not necessary to use stack, because it is a little troublesome to compare the elements in the stack at the last comparison.
Here, the string is directly used as the stack. The string is added and popped at the end. The string has corresponding interfaces. Finally, when comparing, just compare two strings, which is more convenient than comparing the elements in the stack.
The code is as follows:
class Solution {
public:
bool backspaceCompare(string S, string T) {
string s; // When the stack is used
string t; // When the stack is used
for (int i = 0; i < S.size(); i++) {
if (S[i] != '#') s += S[i];
else if (!s.empty()) {
s.pop_back();
}
for (int i = 0; i < T.size(); i++) {
if (T[i] != '#') t += T[i];
else if (!t.empty()) {
t.pop_back();
}
}
if (s == t) return true; // It is much more convenient to directly compare whether two strings are equal than using stack
return false;
}
};
- Time complexity:
O(n + m), n is the length of S and M is the length of T, which can also be understood as the time complexity of O(n)
- Space complexity:
O(n + m) of course, in the above code, you can find that there are repeated logic processing S and processing T. you can separate this common logic. The code is simplified as follows:
class Solution {
private:
string getString(const string& S) {
string s;
for (int i = 0; i < S.size(); i++) {
if (S[i] != '#') s += S[i];
else if (!s.empty()) {
s.pop_back();
}
}
return s;
}
public:
bool backspaceCompare(string S, string T) {
return getString(S) == getString(T);
}
};
Performance remains:
- Time complexity: O(n + m)
- Spatial complexity: O(n + m)
Optimization method (double pointer from back to front)
Of course, the spatial complexity of O(1) can also be used to solve this problem.
At the same time, traverse s and T from back to front (initial I is the end of S, initial j is the end of T), record the number of # and simulate the elimination operation. If # used up, start comparing S[i] and S[j].
The animation is as follows:
If S[i] and S[j] are different, false is returned. If a pointer (I or j) goes to the head of the string first, false is also returned.
The code is as follows:
class Solution {
public:
bool backspaceCompare(string S, string T) {
int sSkipNum = 0; // Record the # quantity of S
int tSkipNum = 0; // Record the # quantity of T
int i = S.size() - 1;
int j = T.size() - 1;
while (1) {
while (i >= 0) { // From back to front, eliminate S#
if (S[i] == '#') sSkipNum++;
else {
if (sSkipNum > 0) sSkipNum--;
else break;
}
i--;
}
while (j >= 0) { // From back to front, eliminate the of T#
if (T[j] == '#') tSkipNum++;
else {
if (tSkipNum > 0) tSkipNum--;
else break;
}
j--;
}
// The latter part # is eliminated. Next, compare s [i]= T[j]
if (i < 0 || j < 0) break; // S or T traverses to the end
if (S[i] != T[j]) return false;
i--;j--;
}
// Description: S and T are traversed at the same time
if (i == -1 && j == -1) return true;
return false;
}
};
- Time complexity: O(n + m)
- Space complexity: O(1)
Other language versions
Java:
// Common method (idea of using stack)
class Solution {
public boolean backspaceCompare(String s, String t) {
StringBuilder ssb = new StringBuilder(); // Simulation stack
StringBuilder tsb = new StringBuilder(); // Simulation stack
// Process two strings separately
for (char c : s.toCharArray()) {
if (c != '#') {
ssb.append(c); // Simulation stack
} else if (ssb.length() > 0){ // You can only play the stack if the stack is not empty
ssb.deleteCharAt(ssb.length() - 1); // Simulated bomb stack
}
}
for (char c : t.toCharArray()) {
if (c != '#') {
tsb.append(c); // Simulation stack
} else if (tsb.length() > 0){ // You can only play the stack if the stack is not empty
tsb.deleteCharAt(tsb.length() - 1); // Simulated bomb stack
}
}
return ssb.toString().equals(tsb.toString());
}
}
python
class Solution:
def get_string(self, s: str) -> str :
bz = []
for i in range(len(s)) :
c = s[i]
if c != '#' :
bz.append(c) # Simulation stack
elif len(bz) > 0: # You can only play the stack if the stack is not empty
bz.pop() # Simulated bomb stack
return str(bz)
def backspaceCompare(self, s: str, t: str) -> bool:
return self.get_string(s) == self.get_string(t)
pass
Go
func getString(s string) string {
bz := []rune{}
for _, c := range s {
if c != '#' {
bz = append(bz, c); // Simulation stack
} else if len(bz) > 0 { // You can only play the stack if the stack is not empty
bz = bz[:len(bz)-1] // Simulated bomb stack
}
}
return string(bz)
}
func backspaceCompare(s string, t string) bool {
return getString(s) == getString(t)
}
JavaScript
// Double stack
var backspaceCompare = function(s, t) {
const arrS = [], arrT = []; // Arrays are used as stacks
for(let char of s){
char === '#' ? arrS.pop() : arrS.push(char);
}
for(let char of t){
char === '#' ? arrT.pop() : arrT.push(char);
}
return arrS.join('') === arrT.join(''); // Compare two strings for equality
};
//Dual stack reduction
var backspaceCompare = function(s, t) {
const getString = s => {
let arrS = [];
for(let char of s){
char === '#' ? arrS.pop() : arrS.push(char);
}
return arrS.join('');
}
return getString(s) === getString(t);
};
//Double pointer
var backspaceCompare = function(s, t) {
let sSkipNum = 0; // Record the # number of s
let tSkipNum = 0; // Record the # quantity of t
let i = s.length - 1, j = t.length - 1;
while(true) {
while(i >= 0){ // From back to front, eliminate s#
if(s[i] === '#') sSkipNum++;
else {
if (sSkipNum > 0) sSkipNum--;
else break;
}
i--;
}
while (j >= 0) { // From back to front, eliminate the of t#
if (t[j] === '#') tSkipNum++;
else {
if (tSkipNum > 0) tSkipNum--;
else break;
}
j--;
}
// The latter part # is eliminated. Next, compare s [i]= t[j]
if (i < 0 || j < 0) break; // s or t traverses to the end
if (s[i] !== t[j]) return false;
i--;j--;
}
// Description: s and t are traversed at the same time
if (i == -1 && j == -1) return true;
return false;
};