LeetCode Top Interview 150 - 125. Valid Palindrome
๐ค ๋ฌธ์ ์ดํด
๋๋ฌธ์์ธ ๋ฌธ์๋ฅผ ์๋ฌธ์๋ก ๋ณ๊ฒฝ ํ ์ซ์์ ์ํ๋ฒณ์ด ์๋ ๊ธ์๋ ์ญ์ + ๋์ด ์ฐ๊ธฐ ํฌํจ
์์์ ์ฝ๋๊ฒ๊ณผ ๋ค์์๋ถํฐ ์ฝ๋๊ฒ ํ๋ฌธ์ผ๋ก ๊ฐ์์ผ ํ๋ค.
๐ค 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()์ ํด๋ ์๋ ๋ฌธ์์ด๊ณผ ๊ฐ์ํ ๋ฐ... ๋ค์์ฑ์๊ฒ ์ฌ๊ณ ํ๋ ๋ฐฉ์์ ๋ฐฐ์์ผ๊ฒ ๋ค ๊ทธ์ ๋ฌธ์ ๋ฅผ ํผ๋ค๊ณ ๊ธ๊ธํ์ง์๊ฒ...
ํญ์ ๊ทธ๋ ๊ฒ ์๊ฐํ์ง๋ง ์๊ฐ๋ณด๋ค ๋ฌธ์ ๋ฅผ ๋ณด๋ฉด ๋นจ๋ฆฌ ํ์ ์๋ ๋ฐฉ๋ฒ๋ง ์ฐพ๋๊ฒ๊ฐ๋ค