In this guide, you will get 844. Backspace String Compare LeetCode Solution with the best time and space complexity. The solution to Backspace String Compare problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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 = “b”
Output: false
Explanation: s becomes “c” while t becomes “b”.
Constraints:
1 <= s.length, t.length <= 200
s and t only contain lowercase letters and '#' characters.
Follow up: Can you solve it in O(n) time and O(1) space?
Complexity Analysis
Time Complexity: O(|\texttt{s}| + |\texttt{t}|)
Space Complexity: O(|\texttt{s}| + |\texttt{t}|)
844. Backspace String Compare LeetCode Solution in C++
class Solution {
public:
bool backspaceCompare(string s, string t) {
return backspace(s) == backspace(t);
}
private:
string backspace(const string& s) {
string stack;
for (const char c : s)
if (c != '#')
stack.push_back(c);
else if (!stack.empty())
stack.pop_back();
return stack;
}
}; /* code provided by PROGIEZ */
844. Backspace String Compare LeetCode Solution in Java
class Solution {
public boolean backspaceCompare(String s, String t) {
return backspace(s).equals(backspace(t));
}
private String backspace(final String s) {
StringBuilder sb = new StringBuilder();
for (final char c : s.toCharArray())
if (c != '#')
sb.append(c);
else if (sb.length() != 0)
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
} // code provided by PROGIEZ
844. Backspace String Compare LeetCode Solution in Python
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def backspace(s: str) -> str:
stack = []
for c in s:
if c != '#':
stack.append(c)
elif stack:
stack.pop()
return stack
return backspace(s) == backspace(t) # code by PROGIEZ
