Backspace String Compare, by LeetCode
Problem is labeled as easy by LeetCode, here it is: https://leetcode.com/problems/backspace-string-compare/description/:
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! Marcelo.
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;
}
}
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! Marcelo.
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;
}
}
Very nice use of the stack, Marcelo! I decided to take advantage of string mutability in C++ and implement a O(N) time and O(1) space algorithm:
ReplyDeleteclass 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
Superb!!!
ReplyDeleteThis comment has been removed by the author.
ReplyDelete