[ALGO] leetcode - 문자열
valid-palindrome
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
// step1. 영어, 숫자 제외 모두 삭제
s = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
// step2. 팰린드롬 체크 -> 투 포인터
let left = 0, right = s.length -1;
while (left <= right) {
if (s[left++] !== s[right--]) return false;
}
return true;
};
reorder-data-in-log-files
풀이
- 문자 로그 -> 숫자 로그 순서로 정렬
- 문자 로그들은 사전 순으로 정렬
- 로그들이 모두 같을 경우 id로 판별
-let3 art zero
,let1 art zero can
인 경우, 길이가 짧은 로그가 앞에 온다. - 숫자 로그는 입력 순서 유지
isNaN(value)
- 입력값이 문자열일 때 숫자 여부 체크를 할 수 있다.
- 단, 공백이나 빈 문자열이 주어질 때는 0으로 치환되어서
false
가 반환된다. - MDN - isNaN()
a.localeCompare(b)
- 문자열
a
와 비교했을 때b
가 전에 오는지, 후에 오는지, 같은 순서인지 알려준다. a
가b
보다 앞에 오면 음수, 뒤에 오면 양수, 같으면 0이 반환된다.
sort([compareFunction])
- 비교함수가
compare(a, b)
일 때, 음수를 반환하면 a가 먼저, 양수가 반환되면 b가 먼저, 0이 반환되면 순서를 유지한다.
let str_arr = ['cyber', 'apple', 'banana']
str_arr.sort(function (a, b) {
return a.localeCompare(b);
});
/**
* @param {string[]} logs
* @return {string[]}
*/
var reorderLogFiles = function(logs) {
let ans = [];
let let_tmp = [];
// step1 문자 로그, 숫자 로그 분할
logs.map(log => {
let [_, ...rest] = log.split(' ');
if(!isNaN(rest[0])) ans.push(log);
else let_tmp.push(log);
});
// step2. 문자 로그 정렬
let_tmp.sort((a, b) => {
const [a_id, ...ta] = a.split(' ');
const [b_id, ...tb] = b.split(' ');
for (let i = 0; i < Math.min(ta.length, tb.length); i++) {
if (ta[i] !== tb[i]) return ta[i].localeCompare(tb[i]);
}
return ta.length - tb.length || a_id.localeCompare(b_id);
})
return [...let_tmp, ...ans];
};
most-common-word
/**
* @param {string} paragraph
* @param {string[]} banned
* @return {string}
*/
var mostCommonWord = function(paragraph, banned) {
// step1. 영어가 아닌 경우 제거, 모두 소문자로 변경, banned 단더 제거
paragraph = paragraph.replace(/[^a-zA-Z ]/g, ' ').toLowerCase()
.split(/\s+/).filter(word => !banned.includes(word));
// step2. 단어 개수 카운팅
let dict = new Map();
paragraph.map(word => {
if (dict.has(word)) dict.set(word, dict.get(word) + 1);
else dict.set(word, 1);
});
const max_len = Math.max(...dict.values());
// step3. 가장 많이 나온 단어 출력
for (const [key, value] of dict) {
if (value === max_len) return key;
}
};
group-anagrams
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
let dict = new Map();
strs.map(str => {
// step1. 단어를 사전순으로 정렬
const sorted_str = str.split('').sort().join('');
// step2. dict 추가
if (!dict.has(sorted_str)) {
dict.set(sorted_str, [str]);
} else dict.set(sorted_str, [...dict.get(sorted_str), str])
});
return [...dict.values()];
};
longest-palindromic-substring
가장 긴 substring부터 탐색해서 팰린드롬이면 함수 종료시킴.
- 시간초과
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
// s의 부분 문자열 중 가장 긴 팰린드롬
let ans = '';
for (let k = s.length; k > 0; k--) {
let i = 0;
while ((i < s.length) && (i + k <= s.length)) {
const tmp = s.substring(i, i + k);
if (tmp === tmp.split('').reverse().join('')) return tmp;
i++;
}
}
};
- 겨우 통과
/**
* @param {string} s
* @return {string}
*/
var isPalindrome = function(s) {
// step1. 영어, 숫자 제외 모두 삭제
s = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
// step2. 팰린드롬 체크 -> 투 포인터
let left = 0, right = s.length -1;
while (left <= right) {
if (s[left++] !== s[right--]) return false;
}
return true;
};
var longestPalindrome = function(s) {
let ans = '';
for (let k = s.length; k > 0; k--) {
let i = 0;
while ((i < s.length) && (i + k <= s.length)) {
const tmp = s.substring(i, i + k);
if (isPalindrome(tmp)) return tmp;
i++;
}
}
};
- 빠른 풀이 - 참고
현재 문자를 기준(센터)으로 생각하고 바깥으로 뻗어가면서 팰린드롬 체크
-> O(N^2)
edge case: 문자열의 길이가 짝수인 경우
var longestPalindrome = function(s) {
let res = s[0];
for (let i = 0; i < s.length; i++) {
// 홀수 길이
let l = i, r = i;
while (l >= 0 && r < s.length && s[l] === s[r]) {
if (r - l + 1 > res.length) res = s.substring(l, r + 1);
l -= 1;
r += 1;
}
// 짝수 길이
l = i, r = i + 1;
while (l >= 0 && r < s.length && s[l] === s[r]) {
if (r - l + 1 > res.length) res = s.substring(l, r + 1);
l -= 1;
r += 1;
}
}
return res;
};
Author And Source
이 문제에 관하여([ALGO] leetcode - 문자열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sqaurelu/ALGO-leetcode-문자열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)