Backspace String Compare

Backspace String Compare is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the String Comparison with Backspaces subpattern.

Problem statement

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?

Topics and companies

Topics: Two Pointers, String, Stack, Simulation.

Reported in interviews at Facebook, Google, Amazon, Oracle.

How to practise Backspace String Compare on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N + M), where N and M are the lengths of s and t respectively. Each character in both strings is visited at most once. time and O(1), since only a constant amount of extra space is used for pointers and counters, and no additional data structures are used. space.

Open Backspace String Compare in the code editor, or read the Backspace String Compare editorial for a worked solution with its approach and complexity analysis.

Where Backspace String Compare sits in the DSA pattern sheet

Problems related to Backspace String Compare

Other problems that use the same String Comparison with Backspaces and Two Pointers techniques:

Preparing this workspace.