[9월] 4주차 스터디

[hyunahOh]

https://leetcode.com/problems/palindromic-substrings/description/

[hyunahOh]

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let i=0;
    let j=0;
    let count=0;

    while (i < s.length) {
        j=0;
        // 홀수
        while (i-j >= 0 && i+j < s.length) {
            if (s[i-j] === s[i+j]) {
                count++;
            } else {
                break;
            }
            j++;
        }

        // 짝수
        j=0;
        while (i-j >= 0 && i+j+1 < s.length) {
            if (s[i-j] === s[i+j+1]) {
                count++;
            } else {
                break;
            }
            j++;
        }
        i++;
    }

    return count;
};

[Choozii]

fail 🥲

/**
 * @param {string} s
 * @return {number}
 */

    const isPalindrome = (s) => {
        let left = 0, right = s.length - 1;

        while(left<right){
            if(s[left] !== s[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

var countSubstrings = function(s) {
    // 부분집합을 구해서 걔가 palindrome인지 체크
    // n^3
    const subsetArr = [];
    let count = 0;

    let isVisit = new Array(s.length).fill(false);

    const dfs = (depth) => {
        if(depth === s.length){
            let subset = "";
            for(let i=0;i<s.length;i++){
                if(isVisit[i]){
                    subset += s[i];
                }
            }
            if(subset){
               subsetArr.push(subset);   
            }
            return;
        }

        isVisit[depth] = true;
        dfs(depth+1);
        isVisit[depth] = false;
        dfs(depth+1);
    }

    dfs(0);

    for(const subset of subsetArr){
        if(isPalindrome(subset)){            
            count++;
        }
    }

    return count;
};

[intothedeep]

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {

    let answer = 0;

    for (let i = 0; i < s.length; i++) {
        const odd = check(s, i, i);
        const even = check(s, i, i + 1);
        answer += odd + even;
    }

    return answer;
};

function check(str, s, e) {

    let cnt = 0;
    while (s >= 0 && e < str.length) {
        if (str[s] !== str[e]) {
            break;
        }
        cnt++;
        s--;
        e++;
    }

    return cnt;
}