[LeetCode] 344. Reverse String (JS)

https://leetcode.com/problems/reverse-string/

Reverse String - LeetCode

핵심 아이디어

• js에 Array.reverse() 가 있으니 그걸 쓰거나...
• left, right two pointer로 양쪽에서 반복하며 swap하면 배열이 뒤집어진다
  • js에서 swap할 때는 destructing asssignment [a,b] = [b,a] 를 활용할 수 있다

 

복잡도

• 시간 복잡도: O(N)
  
  • two pointer로 배열 절반 순회
• 공간 복잡도: O(1)
  
  • left, right 포인터 변수 2개

 

설명

주어진 문자 배열을 in-place, 배열 추가로 만드는 것 없이 O(1)의 공간을 사용하여 뒤집는 문제이다. left, right pointer로 움직이면서 뒤집으면 배열이 뒤집어진다.

이번 문제로 Array.reverse()가 원본 배열을 바꾸는 destructive한 함수임을 알게 되었다. 조심해서 써야겠다

 

코드 (Javascript)

풀이 1...

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    s.reverse();
};

풀이 2 ( Two pointers )

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    let leftIdx = 0;
    let rightIdx = s.length - 1;
    
    while(leftIdx < rightIdx) {
        [s[leftIdx], s[rightIdx]] = [s[rightIdx], s[leftIdx]];        
        
        leftIdx += 1;
        rightIdx -= 1;
    }
};