Given two strings S and T, return 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 = "#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.
Follow up:
- Can you solve it in
O(N)time andO(1)space?
class Solution {
public boolean backspaceCompare(String S, String T) {
return makeString(S).equals(makeString(T));
}
public List<Character> makeString(String str){
List<Character> list = new ArrayList<>();
for(int i=0; i<str.length(); i++){
if(str.charAt(i) == '#'){
if(list.size() > 0){
list.remove(list.size() - 1);
}
}else{
list.add(str.charAt(i));
}
}
//return list.stream().map(e->e.toString()).collect(Collectors.joining());
return list;
}
}class Solution {
public boolean backspaceCompare(String S, String T) {
return makeString(S).equals(makeString(T));
}
public Stack<Character> makeString(String str){
Stack<Character> stack = new Stack();
for(int i=0; i<str.length(); i++){
if(str.charAt(i) != '#'){
stack.push(str.charAt(i));
}else if(stack.size() > 0){
stack.pop();
}
}
//return String.valueOf(stack);
return stack;
}
}[문제] https://leetcode.com/problems/backspace-string-compare/
