1047. Remove All Adjacent Duplicates In String

-https://leetcode.com/problems/verifying-an-alien-dictionary/

Hi! I’m your first Markdown file in StackEdit. If you want to learn about StackEdit, you can read me. If you want to play with Markdown, you can edit me. Once you have finished with me, you can create new files by openi

1차 코드

49 ms	38.5 MB	java

class Solution {
    public String removeDuplicates(String S) {
        // "abbaca"

        if(S.length()<= 1){
            return S;
        }

        char[] chars = S.toCharArray();
        Stack<Character> stack  = new Stack<Character>();
        for(int i=0; i<chars.length; i++){


            if(!stack.isEmpty()) {
                Character cha = stack.peek();
                if (cha != null && cha == chars[i]) {
                    stack.pop();
                    continue;
                }
            }
            stack.push(chars[i]);
        }

        char [] result = new char[stack.size()];
        int index = stack.size()-1;
        while(!stack.isEmpty()){
            Character  last = stack.pop();
            result[index--] = last;
        }

        return new String(result);
    }
}

2차코드

• 자료구조 안쓰고 다시 한번더 풀어봐야겠다.
• 조건이 바로 앞뒤 2개의 character 값만 비교하는거라서 마지막 last index를 기억하는걸로
• 앞뒤가 서로 다를때 last index = currentIndex
• 앞뒤가 서로 같을때 find last index and check index ‘0’

Runtime: 4 ms, faster than 98.11% of Java online submissions for Remove All Adjacent Duplicates In String.
Memory Usage: 37.7 MB, less than 100.00% of Java online submissions for Remove All Adjacent Duplicates In String.

class Solution {
    public String removeDuplicates(String S) {
        // "abbaca"

       if(S.length()<= 1){
            return S;
        }

        char[] chars = S.toCharArray();

        int last = 0;
        for(int i=1; i<chars.length; i++){
            if(last >= 0 && chars[last] == chars[i]){ // 같을때
                chars[i] = '0';
                chars[last] = '0';
                last --;
                while(last >=0 && chars[last] == '0'){
                    last --;
                }
            }else{
                last = i;
            }
        }
        StringBuilder builder = new StringBuilder();
        for(int i=0; i<chars.length; i++){
            if(chars[i] != '0'){
                builder.append(chars[i]);
            }
        }

        return builder.toString();
    }
}

3차코드

Runtime: 3 ms, faster than 99.83% of Java online submissions for Remove All Adjacent Duplicates In String.
Memory Usage: 38.1 MB, less than 100.00% of Java online submissions for Remove All Adjacent Duplicates In String.

• 2차코드에서 StringBilder 제거

// "abbaca"

       if(S.length()<= 1){
            return S;
        }

        char[] chars = S.toCharArray();

        int last = 0;
        int resltLenth = chars.length;
        for(int i=1; i<chars.length; i++){
            if(last >= 0 && chars[last] == chars[i]){ // 같을때
                chars[i] = '0';
                chars[last] = '0';
                last --;
                resltLenth-=2;
                while(last >=0 && chars[last] == '0' ){
                    last --;
                }
            }else{
                last = i;
            }
        }

        char[] result = new char[resltLenth];
        int resultIndex =0;
        for(int i=0; i<chars.length; i++){
            if(chars[i] != '0'){
                result[resultIndex++] = chars[i];
            }
        }
        return new String(result);