LeetCode #844 Backspace String Compare Solution & Explanation

Klook.com
Post Views: 373

LeetCode Problem

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.

Follow up: Can you solve it in O(n) time and O(1) space?

Solution

We can use iteration to simulate the typing event.

In our first solution, we use two simple iteration to find the final result.

C# Solution

Solution1

public class Solution {
    public bool BackspaceCompare(string s, string t) {
        
        string s2 = "";
        int cnt = 0;

        foreach(var a in s){
            if(a == '#'){
                if(cnt>0){
                    cnt-=1;
                    s2 = s2.Substring(0,cnt);
                }

            } else{
                s2 = s2+a;
                cnt+=1;
            }
        }


        string t2 = "";
        cnt = 0;

        foreach(var a in t){
            if(a == '#'){
                if(cnt>0){
                    cnt-=1;
                    t2 = t2.Substring(0,cnt);
                }

            } else{
                t2 = t2+a;
                cnt+=1;
            }
        }
        return s2 == t2;
    }
}

cnt is to count is there any char that can be backspace.

In this solution, there are several areas for improvement.

  • Firstly, the code contains excessive repetition.
  • Secondly, using string operations can be slower compared to utilizing a StringBuilder.

⭐Solution2

public class Solution {
    public bool BackspaceCompare(string s, string t) {
       return BackspaceString(s) == BackspaceString(t);
    }

    private string BackspaceString(string input) {
        var result = new StringBuilder();
        int cnt = 0;    

        foreach (char c in input) {
            if (c == '#') {
                if (cnt > 0) {
                    result.Length--;
                    cnt--;
                }
            } else {
                result.Append(c);
                cnt++;
            }
        }

        return result.ToString();
    }
}

Java Solution

Solution1

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return backspaceString(s).equals(backspaceString(t));
    }

    private String backspaceString(String input) {
        StringBuilder result = new StringBuilder();

        for (char c : input.toCharArray()) {
            if (c == '#') {
                if (result.length() > 0) {
                    result.setLength(result.length() - 1);
                }
            } else {
                result.append(c);
            }
        }

        return result.toString();
    }
}

Python3 Solution

Solution1

class Solution:
    def backspaceString(self,input):
        result = []
        
        for c in input:
            if c == '#':
                if result:
                    result.pop()
            else:
                result.append(c)
        
        return ''.join(result)

    def backspaceCompare(self, s: str, t: str) -> bool:
        return self.backspaceString(s) == self.backspaceString(t)

There is no StringBuilder in python, so we use a list to do the same purpose.

JavaScript Solution

Solution1

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


function backspaceString(input){
    let result = '';

    for (let i = 0; i < input.length; i++) {
        if (input[i] === '#') {
            if (result.length > 0) {
                result = result.slice(0, -1);
            }
        } else {
            result += input[i];
        }
    }

    return result;
}

Conclusion

In this problem, utilizing StringBuilder provides significant benefits, it enables more streamlined and optimized string manipulation.

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts or clicking ads, thanks you~~

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know !!

The problem link : Backspace String Compare – LeetCode

Some Random Posts

Tags

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *