์ฝ”ํ…Œ

LeetCode Top Interview 150 - 125. Valid Palindrome

seo dori 2023. 8. 25. 22:17

๐Ÿค” ๋ฌธ์ œ ์ดํ•ด

๋Œ€๋ฌธ์ž์ธ ๋ฌธ์ž๋ฅผ ์†Œ๋ฌธ์ž๋กœ ๋ณ€๊ฒฝ ํ›„ ์ˆซ์ž์™€ ์•ŒํŒŒ๋ฒณ์ด ์•„๋‹Œ ๊ธ€์ž๋Š” ์‚ญ์ œ + ๋„์–ด ์“ฐ๊ธฐ ํฌํ•จ

์•ž์—์„œ ์ฝ๋Š”๊ฒƒ๊ณผ ๋’ค์—์„œ๋ถ€ํ„ฐ ์ฝ๋Š”๊ฒŒ ํšŒ๋ฌธ์œผ๋กœ ๊ฐ™์•„์•ผ ํ•œ๋‹ค.

 

๐Ÿค” EX

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

 

๐Ÿค” ์˜์‚ฌ ์ฝ”๋“œ

s์— ์ˆซ์ž์™€ ์˜์–ด๊ฐ€ ์•„๋‹Œ ํŠน์ˆ˜๊ธฐํ˜ธ๋ฅผ ๋นผ๋Š”๊ฑด! ์ •๊ทœํ‘œํ˜„์‹์ด์šฉ
let reg = /[`~!@#$%^&*()_|+\-=?;:'",.<>\{\}\[\]\\\/ ]/gim;
let resultData = s.replace(reg, "");
 s.length
 if(s.length%2 == 1){
     splice(s.length/2+1,1)
    for()
    ์–‘ ๋์—์„œ ํ•˜๋‚˜์”ฉ ๊ฐ™์€์ง€ ๋น„๊ตํ•ด์„œ ๋‹ค๊ฐ™์œผ๋ฉด true
    ์•„๋‹ˆ๋ฉด false
 }

 

๐Ÿค” ํ•ด๊ฒฐํ•œ ์ฝ”๋“œ

var isPalindrome = function(s) {
    let reg = /[`~!@#$%^&*()_|+\-=?;:'",.<>\{\}\[\]\\\/ ]/gim;
    let resultData = s.replace(reg, "");   //-> O(n)
    
    resultData=resultData.toLowerCase();    //-> O(n)

    let arr = [...resultData]             //-> O(n)

    if(arr.length % 2 ==1){arr.splice(arr.length/2,1)}

    for(let i =0;i<arr.length;i++){           //-> O(n/2) ๋Œ€๋žต O(n)์œผ๋กœ ๊ฐ„์ฃผ
        if(arr[i]!=arr[arr.length-1-i]){

            return false
        }
    }
    return true
};

 -> ๋Œ€๋žต์  ์‹œ๊ฐ„๋ณต์žก๋„ O(n)

 

๋ฌธ์ œ๋ฅผ ํ’€๊ณ ๋‚˜๋‹ˆ ์˜ค๋Š˜ ๋ฐฐ์šด Two Pointer ํŒจํ„ด์„ ์ด์šฉํ•˜๊ณ  ์žˆ์—ˆ๋‹ค. (์ถ”ํ›„์— ์ •๋ฆฌํ•  ์˜ˆ์ •)

 

 

 

๐Ÿค” ๋‹ค๋ฅธ ํ’€์ด๋ฐฉ๋ฒ•

var isPalindrome = function(s) {
    let newStr = s.replace(/[^a-z0-9]/gi,"").toLowerCase();
    return newStr.split("").reverse().join("") === newStr ? true : false;
};

์‚ฌ์‹ค ์ด๋ฒˆ์— ํ‘ผ ๋ฌธ์ œ๋Š” ๋‚ด๊ธฐ์ค€ ์ฝ”๋“œ๊ฐ€ ๊ธธ๋‹ค๊ณ  ์ƒ๊ฐ๋˜์–ด ๋‹ค๋ฅธ ์‚ฌ๋žŒ๋“ค์˜ ํ’€์ด๋ฅผ ๋ณด๋‹ค๊ฐ€ ์ œ์ผ ๊ฐ„๋‹จํ•œ ํ’€์ด๋ฅผ ๋ด๋ฒ„๋ ธ๋‹ค...

ํšŒ๋ฌธ์œผ๋กœ ๊ฐ™๋‹ค๋ฉด reverse()์„ ํ•ด๋„ ์›๋ž˜ ๋ฌธ์ž์—ด๊ณผ ๊ฐ™์„ํ…๋ฐ... ๋‹ค์–‘์„ฑ์žˆ๊ฒŒ ์‚ฌ๊ณ ํ•˜๋Š” ๋ฐฉ์‹์„ ๋ฐฐ์›Œ์•ผ๊ฒ ๋‹ค ๊ทธ์ € ๋ฌธ์ œ๋ฅผ ํ‘ผ๋‹ค๊ณ  ๊ธ‰๊ธ‰ํ•˜์ง€์•Š๊ฒŒ...

ํ•ญ์ƒ ๊ทธ๋ ‡๊ฒŒ ์ƒ๊ฐํ•˜์ง€๋งŒ ์ƒ๊ฐ๋ณด๋‹ค ๋ฌธ์ œ๋ฅผ ๋ณด๋ฉด ๋นจ๋ฆฌ ํ’€์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•๋งŒ ์ฐพ๋Š”๊ฒƒ๊ฐ™๋‹ค

๋Œ“๊ธ€์ˆ˜0