Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

844. Compares strings containing backspace

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.

 

Example 1:

Input: s = "ab#c", t = "ad#c" output: true explanation: both s and t become "ac".Copy the code

Example 2:

Input: s = "ab##", t = "c#d#" output: trueCopy the code

Example 3:

Input: s = "a##c", t = "#a#c" output: true explanation: both s and t become "c".Copy the code

Example 4:

Input: s = "a#c", t = "b" output: false explanation: s becomes "c", but t is still "b".Copy the code

 

Tip:

  • 1 <= s.length, t.length <= 200
  • s 和 tContains only lowercase letters and charactersThe '#'

 

Advanced:

  • You can useO(N)Time complexity andO(1)Can the spatial complexity solve this problem?

Train of thought

  1. Using the idea of a stack, go to the current stack each timestackIs pushed to the current character, encountered#Remove the last element from the stack;
  2. Separate formattingsandtAnd compare whether the results are the same after formatting;
  3. Since the formatting method is identical, we split it into a common method to reduce redundant code.

implementation

/ * * *@param {string} s
 * @param {string} t
 * @return {boolean}* /
var backspaceCompare = function(s, t) {
    return formatString(s) === formatString(t);
};

function formatString(str) {
    // Iterate through the s string and delete an element when "#" is encountered
    let stack = [];

    const n = str.length;
    for (let i = 0; i < n; i++) {
        if (str[i] === "#") {
            stack.pop();
        } else{ stack.push(str[i]); }}// Returns a formatted string
    return stack.join("");
}
Copy the code

The results of

The results are so average, which is obviously not up to the purpose of our brush. Brush at least 80% of the time, preferably 90%. And they tell us that the progression requires us to use space order 1, which means there are other ways to solve this problem.

To optimize the

So we’re back to the process of finding the pattern, and it’s actually not that hard to say, if you think about it a little bit, matching two strings, the first thing I think of other than using a stack is Pointers, but if we go back and forth, we don’t know if we want to keep the previous elements. Instead, iterate backwards and record the number of elements that need to be removed when # is encountered, and return false if a mismatch is encountered from behind.

Optimize the code

/ * * *@param {string} s
 * @param {string} t
 * @return {boolean}* /
function backspaceCompare(s, t) {
    let n = s.length - 1, m = t.length - 1;

    // Iterate from the last to the first
    while (n >= 0 && m >= 0) {
        // Perform the delete if necessary
        n = getFirstChart(s, n);
        m = getFirstChart(t, m);

        // Start pairing
        if(s[n] ! == t[m]) {return false;
        }

        // Take it away, next
        n--;
        m--;
    }

    // check if both zeros are 0, there may be a residual "a#", so perform one more delete check
    return n === m || getFirstChart(s, n) === getFirstChart(t, m);
};

// Find the first valid character
function getFirstChart(str, len) {
  // Records how many elements are to be deleted
  let count = 0;

  // Delete forward when the delete symbol is encountered
  // &&len > -1 means: if the first element is deleted, return directly
  while ((str[len] === "#" || count > 0) && len > -1) {
    count = str[len] === "#" ? count + 1 : count - 1;
    len--;
  }

  return len;
}
Copy the code

The optimization results

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.