Problem: Given two strings S and T, return 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".
Approach: This can be easily solved using the stack but obviously the downside is extra space. You can see the implementation.
Let's try to reduce space. We can't traverse the string from start to end as whenever we see a backspace we need to remove the character and it will be expensive so instead of start to end, we will traverse the string from end to start. Whenever we see '#' we increase the count of backspace by 1 and if we see a character then we check if backspace count is 0 then we put the character in the result otherwise we reduce the backspace count by 1.
That's all!
Implementation in C#:
Approach 1: Parsing string from the end to start
public bool BackspaceCompare(string S, string T)
{
string SChas = this.GetResultString(S);
string TChars = this.GetResultString(T);
return SChas == TChars;
}
private string GetResultString(string str)
{
int bkSpCount = 0;
StringBuilder stringBuilder = new StringBuilder();
for (int i = str.Length - 1; i >= 0; --i)
{
if (str[i] == '#')
{
++bkSpCount;
}
else
{
if (bkSpCount == 0)
{
stringBuilder.Append(str[i]);
}
else
{
--bkSpCount;
}
}
}
return stringBuilder.ToString();
}
Approach 2: Using Stack
public bool BackspaceCompare(string S, string T)
{
char[] SChars = this.GetResultString(S);
char[] TChars = this.GetResultString(T);
if (SChars.Length != TChars.Length)
{
return false;
}
for (int i = 0; i < SChars.Length; ++i)
{
if (SChars[i] != TChars[i])
{
return false;
}
}
return true;
}
private char[] GetResultString(string str)
{
Stack<char> stack = new Stack<char>();
foreach (char ch in str)
{
if (ch == '#')
{
if (stack.Count > 0)
{
stack.Pop();
}
}
else
{
stack.Push(ch);
}
}
char[] result = new char[stack.Count];
for (int i = result.Length - 1; i >= 0; --i)
{
result[i] = stack.Pop();
}
return result;
}
Complexity: O(n)
No comments:
Post a Comment