844. Backspace String Compare
1. Description
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.
2. Example
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”.
3. Note
- 1 <= S.length <= 200
- 1 <= T.length <= 200
- S and T only contain lowercase letters and ‘#’ characters.
4. Follow Up
- Can you solve it in O(N) time and O(1) space?
5. Solutions
My Accepted Solution
n = max(i_str1.size(), i_str2.size())
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// bool backspaceCompare(string S, string T)
bool backspaceCompare(const string &i_str1, const string &i_str2)
{
stack<int> processedString1, processedString2;
for(int i = 0; i < i_str1.size(); i++)
{
if(i_str1[i] == '#' && !processedString1.empty()) processedString1.pop();
else if(i_str1[i] != '#') processedString1.push(i_str1[i]);
}
for(int i = 0; i < i_str2.size(); i++)
{
if(i_str2[i] == '#' && !processedString2.empty()) processedString2.pop();
else if(i_str2[i] != '#') processedString2.push(i_str2[i]);
}
return processedString1 == processedString2;
}
};
5.1 Two Pointers(Follow Up)
n = max(i_str1.size(), i_str2.size())
Time complexity: O(n)
Space complexity: O(1)
// if we want to make the space complexity O(1), we can't use stack or other thing to store elements
// so we use two pointers, just go thtought the array and judge them
// if we go through the array from left to right, we have to check the later '#' to decide current element
// so we go through the array from right to left
class Solution
{
public:
// bool backspaceCompare(string S, string T)
bool backspaceCompare(const string &i_str1, const string &i_str2)
{
for(int i = i_str1.size() - 1, j = i_str2.size() - 1, skipI = 0, skipJ = 0; i >= 0 || j >= 0; i--, j--)
{
while(i >= 0)
{
if(i_str1[i] == '#')
{
skipI++;
i--;
}
else if(skipI > 0)
{
skipI--;
i--;
}
else
{
break;
}
}
while(j >= 0)
{
if(i_str2[j] == '#')
{
skipJ++;
j--;
}
else if(skipJ > 0)
{
skipJ--;
j--;
}
else
{
break;
}
}
if(i >= 0 && j >= 0 && i_str1[i] != i_str2[j]) // they have a different char
return false;
if((i >= 0) != (j >= 0)) // only one of them ends
return false;
}
return true;
}
};