Leetcode

# 844. Backspace String Compare

by hooni posted May 05, 2020
?

#### 단축키

Prev이전 문서

Next다음 문서

ESC닫기

크게 작게 위로 아래로 댓글로 가기 인쇄

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 <= 200`
• `1 <= T.length <= 200`
• `S` and `T` only contain lowercase letters and `'#'` characters.

• Can you solve it in `O(N)` time and `O(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{
}
}

//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;
}
}```

1 2 3 4