LeetCode[day9] - Backspace String Compare

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.

Note:
1 <= S.length <= 2001 <= T.length <= 200S and T only contain lowercase letters and '#' characters.

Follow up:
Can you solve it in O(N) time and O(1) space?

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 후입선출, 나중에 들어온게 먼저 지워져야한다.

 - Stack을 사용하면 적당할 것이라고 생각을 했다.

 - 그리고 String을 나누기 위해서 toCharArrary()를 사용하고, stack에 값을 추가해준다.

 - 검사하려는 값이 '#'라면, stack에서 뺀다.

 - stack을 정제한다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 어려웠던 점은 정말 없었다.

 - 자료구조 고르는 것도 쉬웠고, 이전에 String을 분해하고, 결합하는 과정을 진행해서 쉬웠다.

 - 하지만, 문제에서 주어진 Follow Up을 충족할까?, 이것은 고민이었다.

 

3. 내가 작성한 알고리즘

 

class Solution {
    public boolean backspaceCompare(String S, String T) {
        String resultS = processLogic(S);
        String resultT = processLogic(T);
        return resultS.equals(resultT);
    }
    
    private String processLogic(String input){
        Stack<Character> stack = new Stack();
        
        for(Character character : input.toCharArray()){
            if(character == '#'){
                if(stack.size() != 0) stack.pop();
            }else{
                stack.add(character);
            }
        }
        char[] stackContents = new char[stack.size()];
        int stackCount = 0;
        while(stack.size() != 0){
            stackContents[stackCount] = stack.pop();
        }
        return String.valueOf(stackContents);
    }
}

4. 내가 작성한 알고리즘 결과

오..생각보다 괜찮을지도?

5. 다른 사람이 작성한 알고리즘 보고, 내 알고리즘 간단하게 하기

 

 - 우선, stack을 String.valueOf(stack)으로 하게 되면, 쉽게 stack의 내용을 string으로 바꿀 수 있다는 사실을 알았다.

 - 그러면서, stackContents라는 stack을 담아두는 char[]의 배열을 제거할 수 있게 되었다.

 - 그런데, 속도는 더 느려졌다. 왜일까.. 궁금하다.

 

class Solution {
    public boolean backspaceCompare(String S, String T) {
        String resultS = processLogic(S);
        String resultT = processLogic(T);
        return resultS.equals(resultT);
    }
    
    private String processLogic(String input){
        Stack<Character> stack = new Stack();
        
        for(Character character : input.toCharArray()){
            if(character == '#'){
                if(stack.size() != 0) stack.pop();
            }else{
                stack.add(character);
            }
        }
        return String.valueOf(stack);
    }
}

 

6. 다른 사람의 알고리즘 결과

 

 String.valueOf(Stack)을 하게 되면, 내부적으로 어떤 일을 할까?

잘 모르겠지만, toString()을 하는 과정에서 약간의 추가 작업을 진행하면서, 약간 느려졌다.

아주, 눈꼽만큼 느려졌다.

 

7. Follow Up?

 

 - 우선 해당 문제를 풀기 위해서, Stack을 하나 추가했으니, Stack의 사이즈인 O(N)의 공간복잡도가 된다.

 - 속도는 for문을 n개 만큼 돌리니, O(N)의 시간복잡도가 된다.

 - 해당 문제는, O(N) : O(N)의 시간, 공간 복잡도를 갖는다.

 

8. 진짜 정답은?

 

- input된 String으로만 해당 알고리즘을 해결했으니, O(1)의 공간복잡도이다.

- 해당 로직이 O(N)의 시간복잡도 인지는 모르겠다. 하지만, 런타임이 가장 빠르니 O(N)이겠지.

 

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) { // While there may be chars in build(S) or build (T)
            while (i >= 0) { // Find position of next possible char in build(S)
                if (S.charAt(i) == '#') {skipS++; i--;}
                else if (skipS > 0) {skipS--; i--;}
                else break;
            }
            while (j >= 0) { // Find position of next possible char in build(T)
                if (T.charAt(j) == '#') {skipT++; j--;}
                else if (skipT > 0) {skipT--; j--;}
                else break;
            }
            // If two actual characters are different
            if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j))
                return false;
            // If expecting to compare char vs nothing
            if ((i >= 0) != (j >= 0))
                return false;
            i--; j--;
        }
        return true;
    }
}

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3291/

Explore - LeetCode