Sponsored
Sponsored
This approach simulates the typing process using two stacks, one for each string. We iterate over each string, using the stack to build the string as it would appear after considering the backspace characters ('#'). By comparing the final stack representations, we can determine if the two strings are equivalent.
Time Complexity: O(n + m), where n and m are the lengths of s and t. Each character is processed once.
Space Complexity: O(n + m) due to the auxiliary arrays used to store the processed results of s and t.
1import java.util.Stack;
2
3public class BackspaceStringCompare {
4 public boolean backspaceCompare(String s, String t) {
5 return buildFinalString(s).equals(buildFinalString(t));
6 }
7
8 private String buildFinalString(String str) {
9 Stack<Character> stack = new Stack<>();
10 for (char ch : str.toCharArray()) {
11 if (ch != '#') {
12 stack.push(ch);
13 } else if (!stack.isEmpty()) {
14 stack.pop();
15 }
16 }
17 StringBuilder result = new StringBuilder();
18 while (!stack.isEmpty()) {
19 result.append(stack.pop());
20 }
21 return result.reverse().toString();
22 }
23
24 public static void main(String[] args) {
25 BackspaceStringCompare solution = new BackspaceStringCompare();
26 System.out.println(solution.backspaceCompare("ab#c", "ad#c")); // true
27 System.out.println(solution.backspaceCompare("ab##", "c#d#")); // true
28 System.out.println(solution.backspaceCompare("a#c", "b")); // false
29 }
30}The Java solution uses a stack to construct the final string. Each character is pushed if it's not a '#', and the top of the stack is popped if a '#' is encountered and the stack is not empty. We then build the final string by popping all characters from the stack. The two strings are compared by their final constructed forms.
This approach avoids extra space by using two pointers to traverse the strings backwards. By skipping over characters that are effectively backspaced due to a '#' character, we can compare corresponding positions in each string without actually building the resultant strings.
Time Complexity: O(n + m), where n and m are the lengths of s and t.
Space Complexity: O(1), since we only use constant space.
1
class Program {
static bool BackspaceCompare(string s, string t) {
int si = s.Length - 1, ti = t.Length - 1;
int skipS = 0, skipT = 0;
while (si >= 0 || ti >= 0) {
while (si >= 0) {
if (s[si] == '#') { skipS++; si--; }
else if (skipS > 0) { skipS--; si--; }
else break;
}
while (ti >= 0) {
if (t[ti] == '#') { skipT++; ti--; }
else if (skipT > 0) { skipT--; ti--; }
else break;
}
if ((si >= 0 && ti >= 0 && s[si] != t[ti]) || ((si >= 0) != (ti >= 0))) {
return false;
}
si--; ti--;
}
return true;
}
static void Main(string[] args) {
Console.WriteLine(BackspaceCompare("ab#c", "ad#c")); // true
Console.WriteLine(BackspaceCompare("ab##", "c#d#")); // true
Console.WriteLine(BackspaceCompare("a#c", "b")); // false
}
}This C# solution employs a two-pointer method. By moving pointers from the end to the front of the strings, it handles backspaces in constant space without actually modifying the input strings themselves. Characters are checked for equality only after confirming they are the visible characters after simulating backspace deletions.