LeetCode - Valid Palindrome

LANA·2020년 9월 10일
0

알고리즘

목록 보기
3/3

LeetCode - Valid Palindrome

첫번째 시도

  1. 문자열의 길이가 홀수일 경우/짝수일 경우를 구분하여 문자열을 반으로 자른다
  2. 두번째 잘라진 문자열을 뒤집어서(split, reverse 사용) 첫번째 문자열과 비교하고 boolean 반환
  3. 홀수일 경우는 통과했지만 짝수일 때 시간이 초과되었다.

두번째 시도

  1. 원섭님이 palindrome linked list 사용할 때 쓰셨던 방법을 응용해보았다.
  2. for문 안에서 i와 j를 선언하여, 각각 문자열의 첫값과 끝값을 비교하면서 만나게하는 로직이었다.
  3. 우선 이렇게 시도할 경우 문제가 풀리지 않았고, mid라는 별도의 변수를 선언하여야 했는데, 이렇게 될 시에 아래의 로직은 홀수인 경우에만 boolean을 반환하여 짝수인 경우의 식을 따로 작성해야 한다는 번거로움이 있었다.
let mid = Math.floor(onlyStr.length) -1
    for(let i=0,j=onlyStr.length-1; i<mid,j>=mid; i++,j--) {
        if(onlyStr[i] !== onlyStr[j]) {
            return false
        }
    }
    return true

세번째 시도(마지막)

  1. discuss 게시판에 나와있는 내용이었는데, 위 과정(두번째 시도)이 있어서 아래의 while문을 이해할 수 있었다.
  2. 조건문이 엄청 깔끔해졌다...
  3. replace메소드 + 정규표현식을 사용하여 특수문자를 제거하는 식도 있었는데... 정규표현식도 공부해야겠다.
var isPalindrome = function(s) {
    
    s = s.toLowerCase().split('')
    let onlyStr = ''
    let allChars ='abcdefghijklmnopqrstuvwxyz1234567890'
    s.filter(char => {
        if(allChars.includes(char)) {
            return onlyStr += char
        }
    })
    
    let i=0; let j=onlyStr.length-1;
    while(i<j) {
        if(onlyStr[i] !== onlyStr[j]) 
            return false
            i++;
            j--;   
    }
    return true
};
profile
Let's code like chord !

0개의 댓글