Compares strings that contain backspace

LeetCode portal 844. Backspace String Compare

The title

Given two strings, s and t, when each is entered into a blank text editor, determine whether the two are equal. # stands for backspace character.

Return true if equal; Otherwise, return false.

Note: If you enter a backspace character for empty text, the text remains empty.

Given two strings s and t, return true if they are equal when both are typed into empty text editors. ‘#’ means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example :

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".


Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".


Input: s = "a##c", t = "#a#c"
Output: true
Explanation: Both s and t become "c".


Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".
Copy the code

Constraints:

  • 1 <= s.length, t.length <= 200
  • s and t only contain lowercase letters and ‘#’ characters.

Thinking line

Their thinking

So what do we need to do in addition to dealing with lowercase characters? That’s the special character #. The # is a delete operation that removes the previous character.

So how do we handle this particular operation?

We use a stack data structure to hold the data after special characters have been processed. Because the stack has typical FILO characteristics. Can save the character in the title very well.

So let’s loop through s and t first. if

  • Traversal to character, directlypushTo the correspondingstack
  • To traverse the#, the implementation ofstack.pop()

To sum up, we can be smart when we type code.

/ * * *@param {string} s
 * @param {string} t
 * @return {boolean}* /
var backspaceCompare = function (s, t) {
    const sStack = [];
    const tStack = []

    for (let i = 0; i < s.length; i++) {
        if (s[i] === The '#') {
            sStack.length && sStack.pop();
        } else{ sStack.push(s[i]); }}for (let j = 0; j < t.length; j++) {
        if (t[j] === The '#') {
            tStack.length && tStack.pop()
        } else {
            tStack.push(t[j])
        }
    }
    return sStack.join(' ') === tStack.join(' ');
};
Copy the code

This is my solution to this question. If you have any questions or better solutions, please leave a comment and interact.