[알고리즘] LeetCode_#151

151. Reverse Words in a String

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

✨ Example

🚨 Constraints

▶︎ 풀이

345. Reverse Vowels of a String 의 풀이 응용

1. 주어진 문자열을 " "(공백문자)를 기준으로 나눈 후(split) 시작 포인터와 끝 포인터를 두어 서로 위치를 변경함
2. 변경 후 포인터의 위치를 이동시킴 (start++, end--)

루프 내부에서 위의 결과로 뒤집힌 문자 배열을 붙인다. 이 때, 요소 사이에 " " 을 넣는다.

• 예시3: 공백문자가 여러 개 일때 하나의 공백문자로 줄인다.
  → 루프에서 배열 안의 요소(string)가 공백이 아닐 경우만 결과 문자열에 포함

▶︎ 기존코드

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        String[] str = s.split(" ");
        int start = 0;
        int end = str.length - 1;
        while (start < end) {
            String temp = str[start];
            str[start] = str[end];
            str[end] = temp;
            start++;
            end--;
        }
        for (String string : str) {
            if(!string.isEmpty()){
                sb.append(string).append(" ");
            }
        }
        return sb.toString().trim();
    }
}

▶︎ 개선사항

실행속도(Runtime), 메모리 효율(Memory)

1. 포인터 이동 및 위치 전환에 사용한 while문, 결과 문자열을 만들기 위한 for문이 있어 비교적 실행 속도와 메모리 효율이 떨어짐
   → 리펙토링: 하나의 반복문만 사용하도록 코드 수정

2. 정규 표현식 사용

   • \s : 공백문자(스페이스, 탭, 줄바꿈)
   • +: 1회 이상 반복

   s.split("\\s+"): 1회 이상의 공백문자를 기준으로 split

▶︎ 수정코드

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        String[] words = s.split("\\s+");
        StringBuilder result = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            result.append(words[i]);
            if (i > 0) {
                result.append(" ");
            }
        }
        return result.toString();
    }
}