Backspace String Compare, by LeetCode

Problem is labeled as easy by LeetCode, here it is: https://leetcode.com/problems/backspace-string-compare/description/:

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.
Example 1:
Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".
Example 2:
Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".
Example 3:
Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".
Example 4:
Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

My solution won't be the most efficient - it will run in O(n)-time and O(n)-space. There is a way to do in O(1)-space but this is a straightforward problem to use a stack that I decided to use it as an example of stack usage. It boils down to a simply push and pop, recreation of the string afterwards, and comparison. Code passed (#235 for me on LeetCode). Many cheers! Boris.

public class Solution
{
public bool BackspaceCompare(string S, string T)
{
return Process(S).Equals(Process(T));
}

private string Process(string s)
{
Stack<char> stack = new Stack<char>();

foreach (char c in s)
{
if (c != '#') stack.Push(c);
else if (stack.Count > 0) stack.Pop();
}
string retVal = "";
while (stack.Count > 0) retVal = ((char)stack.Pop()).ToString() + retVal;

return retVal;
}
}


Comments

  1. Very nice use of the stack, Boris! I decided to take advantage of string mutability in C++ and implement a O(N) time and O(1) space algorithm:

    class Solution {
    private:
    int process(string& str) {
    int out = 0;
    for (int i = 0; i < str.size(); ++i) {
    if (str[i] == '#') {
    out = max(0, out-1);
    } else {
    str[out++] = str[i];
    }
    }
    return out;
    }
    public:
    bool backspaceCompare(string& S, string& T) {
    int s_end = process(S);
    int t_end = process(T);
    return s_end == t_end && equal(S.cbegin(), S.cbegin() + s_end, T.cbegin());
    }
    };

    It does not use a stack, but a classic two pointer approach to write characters at to their destination index.

    Cheers,
    Taras

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons