[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;
};