Given two strings S and T, return if they are equal when both are typed into empty text editors. # 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".
Note:
1 <= S.length <= 2001 <= T.length <= 200SandTonly contain lowercase letters and'#'characters.
Solution
The solution is pretty simple to this one. We need to process each String and then compare the end result. To process each string we can use Stack, push an element is its not “#”, else pop the last element. Both time and space complexity for this solution will be O(m+n), if m and n are string lengths.
class BackSpaceStringCompare {
public boolean backspaceCompare(String S, String T) {
// Find the string after processing both S and T and compare them
return processString(S).equals(processString(T));
}
public String processString(String S){
//Initialize a stack
Stack<Character> s = new Stack<>();
//Traverse through the String one character at a time
for(char ch: S.toCharArray()){
//if character is equal to #, then pop an element if stack is not empty
if(ch == '#'){
if(!s.isEmpty())
s.pop();
}
// else push character to stack
else
s.push(ch);
}
//return the string generated by stack
return s.toString();
}
}
Code – BackSpaceStringCompare.java
Source – leetcode