[leetcode #917] Reverse Only Letters

Problem

Given a string s, reverse the string according to the following rules:

All the characters that are not English letters remain in the same position.
All the English letters (lowercase or uppercase) should be reversed.
Return s after reversing it.

Example 1:

Input: s = "ab-cd"
Output: "dc-ba"

Example 2:

Input: s = "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: s = "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Constraints:

・ 1 <= s.length <= 100
・ s consists of characters with ASCII values in the range [33, 122].
・ s does not contain '\"' or '\\'.

Idea

알파벳을 제외한 다른 문자는 원래 위치 그대로 둔 뒤, 알파벳만 역순으로 만드는 문제다. 주어진 string을 탐색하면서 알파벳일 경우 stack에, 알파벳이 아닐 경우 list에 해당 문자의 index를 저장하도록 했다. 이후 reverse된 string을 만들 때는 list의 가장 앞쪽에 있는 index가 현재 string의 길이와 같을 경우 해당 문자를 더하고, 아닐 경우 stack에서 알파벳을 꺼내 더했다.

알고리즘은 다음과 같다.

1. 알파벳일 경우 stack에, 알파벳이 아닌 문자일 경우 해당 문자의 index를 리스트에 더한다.
2. stack과 list가 빌 때까지 새로운 string에 문자를 더한다.
   a. list의 가장 앞쪽에 있는 인덱스가 만들고 있는 string의 길이와 같을 경우 알파벳이 아닌 문자이므로 똑같은 위치에 넣어준다.
   b. a와 같은 상황이 아닐 경우 stack에서 알파벳을 꺼내어 넣어준다.
3. 만들어진 string을 리턴한다.

Solution

class Solution {
    public String reverseOnlyLetters(String s) {
    	List<Integer> nonCharList = new LinkedList<>();
        Stack<Character> stack = new Stack<>();

        for (int i=0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')) {
                stack.push(c);
            } else {
                nonCharList.add(i);
            }
        }

        int len = 0;
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty() || !nonCharList.isEmpty()) {
            if (!nonCharList.isEmpty() && nonCharList.get(0) == len) {
                sb.append(s.charAt(nonCharList.remove(0)));
            } else if (!stack.isEmpty()){
                sb.append(stack.pop());
            }
            len++;
        }

        return sb.toString();
    }
}

사실 이렇게 복잡하게 할 필요없이 알파벳일 경우에만 stack에 넣어주고 주어진 string을 재탐색하여 알파벳이 아니면 stack을 뒤질 필요없이 해당 문자를 그대로 넣어주면 된다.

class Solution {
    public String reverseOnlyLetters(String S) {
    	Stack<Character> letters = new Stack();
        for (char c: S.toCharArray())
            if (Character.isLetter(c))
                letters.push(c);

        StringBuilder ans = new StringBuilder();
        for (char c: S.toCharArray()) {
            if (Character.isLetter(c))
                ans.append(letters.pop());
            else
                ans.append(c);
        }

        return ans.toString();
    }
}

Reference

https://leetcode.com/problems/reverse-only-letters/