917. Reverse Only Letters

문제

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

정답

1. 처음 풀이(two pointers + isAlphabetic())

class Solution {
    public String reverseOnlyLetters(String s) {
        char[] arr = s.toCharArray();
        int lt = 0;
        int rt = s.length()-1;

        while(lt < rt) {
            if(!Character.isAlphabetic(arr[lt])) {
                lt++;
                continue;
            } 
            if(!Character.isAlphabetic(arr[rt])) {
                rt--;
                continue;
            }
            // 아닌 경우에만 swap 진행
            char tmp = arr[lt];
            arr[lt] = arr[rt];
            arr[rt] = tmp;
            lt++;
            rt--;
        }
        return new String(arr);
    }
}

• StringBuilder의 reverse()를 사용하기엔 뒤집는 조건이 있기 때문에 무리
• 문자열을 뒤집는다 - two pointers로 하나씩 직접 바꿔나가기 (O(N))
• 조건 : 영어인 경우엔 뒤집고, 영어가 아닌 경우엔 그대로 두기
  • Character.isAlphabetic()으로 char가 알파벳인지 아닌지 확인
  • 아스키 코드로도 확인 가능 (대문자 65~90, 소문자 97~122)
    • 아스키 코드로 확인하는 경우에, toUpperCase나 tolowerCase로 대/소문자로 획일화한 후 처리하는 것이 편리
• 앞과 뒤의 문자를 바꾸는 것이므로 in-place 정렬이 편할듯! (char 배열 사용)
  • 서로의 위치를 바꾸는 것이기 때문에 StringBuilder를 사용해서 하나씩 더해주는 것은 불가능
    
• 시간 복잡도 O(N), 공간 복잡도 O(N)의 풀이
  • 문자열의 앞 뒤를 바꾸는 것이기 때문의 별도의 배열이 필수라 생각됨