[leetcode] 345. Reverse Vowels

 

문제

 

최초 풀이 (시간 복잡도 O(n))

1. stack을 이용해서 문자열 s의 for문을 돌며 vowel을 따로 저장

2. 문자열 s의 for문을 돌며 문자열 s의 vowel 부분에 stack의 pop으로 하나씩 꺼내서 문자열을 완성함.

 

최종 풀이 -> two pointer 사용, start = 0, end = s.length() - 1 부터 시작해서 각각이 모음을 발견하면 swap할 수 있도록 함.

(참고한 풀이에서 시간 복잡도가 O(n)이라고 했는데 좀 생각해봐야할 부분)

최초 풀이

class Solution {
    public String reverseVowels(String s) {
        List<Character> vowels = new ArrayList<>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');

        vowels.add('A');
        vowels.add('E');
        vowels.add('I');
        vowels.add('O');
        vowels.add('U');

        Stack<Character> vowelCha = new Stack<>();

        for(int i = 0; i < s.length(); i++) {
            if (vowels.contains(s.charAt(i))) {
                vowelCha.push(s.charAt(i));
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++) {
            if (vowels.contains(s.charAt(i))) {
                sb.append(vowelCha.pop());
                continue;
            }
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

 

최종 풀이

class Solution {
    public String reverseVowels(String s) {
        int start = 0;
        int end = s.length() - 1;
        String vowels = "aeiouAEIOU";
        String[] words = s.split("");

        while(start < end) {
            while (start < end && vowels.indexOf(words[start]) == -1) {
                start++;
            }

            while(start < end && vowels.indexOf(words[end]) == -1) {
                end--;
            }

            String temp = words[start];
            words[start] = words[end];
            words[end] = temp;

            start++;
            end--;
        }

        return String.join("", words);
    }
}