Let’s discuss an interesting problem Backspace String Compare.
Given two strings S and T containing backspaces. We have to write a code to check if they are equal. In string, # means a backspace character.
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”.
We have discussed the problem statement. Before checking the solution, spend a few minutes to think how you can approach this problem.
In this tutorial, I am going to discuss multiple approaches to solve this problem. Also, at the end of this post, i have shared the link to the video tutorial.
Backspace String Compare Solution using Stack | Java Code
The simplest approach to solve this problem is to use two stacks. Here are the following steps –
i) Declare two stacks.
ii) Perform the following operations for both the strings.
a) Traverse a string and pick one character at a time. If the character is not a backspace character (#) then push them into a stack.
b) If it’s a backspace character then pop out the last pushed character from a stack.
iii) After that compare both the stacks. If both are equal then return true else false.
The time complexity of this approach is O(n) and its space complexity is also O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
//Backspace String Compare using Stack public class BackspaceStringCompare { public static boolean backspaceCompareUsingStack(String S, String T) { Stack<Character> st1 = backspaceOperationWithStack(S); Stack<Character> st2 = backspaceOperationWithStack(T); return st1.equals(st2); } private static Stack<Character> backspaceOperationWithStack(String str) { Stack<Character> st = new Stack<>(); //Traverse a string for(int i = 0; i < str.length(); i++) { char ch = str.charAt(i); /* If current char is not a backspace, then push them in a stack. Else pop the last pushed character from a stack. */ if(ch != '#') { st.push(ch); } else if (!st.isEmpty()){ st.pop(); } } return st; } public static void main(String[] args) { String str1 = "a##c"; String str2 = "#a#c"; boolean result = backspaceCompareUsingStack(str1, str2); System.out.println(result); } } |
Backspace String Compare using Two Pointers – Java Code
In our previous approach, we have solved this problem using the stack data structure. Can we optimize our solution?
Yes, we can solve this problem using two pointers without using extra space.
Here are the following steps –
Traverse both the strings in reverse order. If any backspace(#) character is found, It means we have to skip the next non-backspace character. If a character isn’t skipped, it is part of the final answer.
The time complexity of this approach is O(n) and its space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
//Backspace String Compare without using Any Extra Space public class BackspaceStringCompare { public static boolean backspaceCompareUsingPointer(String S, String T) { int idx1 = S.length()-1; int idx2 = T.length()-1; while(idx1 >= 0 || idx2 >= 0) { idx1 = backspaceOperationWithPointer(S, idx1); idx2 = backspaceOperationWithPointer(T, idx2); if (idx1 >= 0 && idx2 >= 0 && S.charAt(idx1) != T.charAt(idx2)) return false; if ((idx1 >= 0) != (idx2 >= 0)) return false; idx1--; idx2--; } return true; } private static int backspaceOperationWithPointer(String str, int i) { int skip = 0; while (i >= 0) { if (str.charAt(i) == '#') { skip++; i--; } else if (skip > 0) { skip--; i--; } else break; } return i; } public static void main(String[] args) { String str1 = "a##c"; String str2 = "#a#c"; boolean result = backspaceCompareUsingPointer(str1, str2); System.out.println(result); } } |
Backspace String Compare Video Tutorial
Programming Questions on Arrays
