Portfolio

📄문제

✏️풀이

은찬


const getPalindromeLength = (s, left, right) => {
    while(left >= 0 && right < s.length){
        if(s[left] !== s[right]){
            break;
        }
        
        left--;
        right++;
    }
    
    return right - (left + 1);
}

const longestPalindrome = (s) => {
    let start = 0;
    let end = 0;
    
    if(s.length === 1){
        return s;
    }
    
    for(let i = 0; i < s.length; i++){
        const len1 = getPalindromeLength(s, i, i);
        const len2 = getPalindromeLength(s, i, i + 1);
        
        if(end - start + 1 < len1){
            start = i - Math.floor(len1 / 2);
            end = i + Math.floor(len1 / 2);
        }
        
        if(end - start + 1 < len2){
            start = i + 1 - Math.floor(len2 / 2);
            end = i + Math.floor(len2 / 2);
        }
    }
    
    return s.substr(start, end - start + 1);
};

현석

첫번쨰 풀이 (런타임 에러)


var longestPalindrome = function(s) {
  const dp = Array.from({length: s.length + 1}, () => [])
  let max = s[0]
  s.split('').forEach((char, i) => {
    dp[1].push({
      str: char,
      start: i,
      end: i
    })
        
    if (s.length > 1 && i !== s.length - 1 && s[i] === s[i+1]) {
      dp[2].push({
        str: char + s[i + 1],
        start: i,
        end: i + 1 
      })
      max = char + s[i + 1]
    } 
  })
  
  for (let i = 1; i <= s.length-2; i++) {
    dp[i].forEach(({str, start, end}) => {
      if (start === 0 || end === s.length -1) {
        dp[i+2].push({str, start, end})
        return
      } 
      const prevChar = s[start -1]
      const nextChar = s[end + 1]
      
      if (prevChar === nextChar) {
        dp[i+2].push({
          str: prevChar + str + nextChar,
          start: start - 1,
          end: end + 1
        })
        max = prevChar + str + nextChar
      } else {
        dp[i+2].push({str, start, end})
      }
    })    
  }  
  return max
};

두번쨰 풀이(역시 에러)


var longestPalindrome = function(s) {
  const dp = Array.from(
    {length: s.length}, 
    (_, i) => Array.from({length: s.length}, (_, j) => (i === j ? s[i] : false)))
  let maxPalindrome = s[0]
  
  s.split('').forEach((c, i) => {
    if(i === s.length - 1) return
    if(c === s[i + 1]) {
      dp[i][i+1] = c + c
      maxPalindrome = c + c
    } 
  })
  
  for (let i=1; i <s.length -1 ; i++) {
    for (let j=i; j <s.length - 1 ; j++) {
      const startIdx = i < j ? i : j
      const endIdx = i < j ? j : i
      
      const prevChar = s[startIdx - 1]
      const nextChar = s[endIdx + 1]
      if (dp[i][j] && s[startIdx - 1] === s[endIdx + 1]) {
        const newPalindrome = prevChar + dp[i][j] + nextChar
        dp[startIdx-1][endIdx+1] = newPalindrome
        dp[endIdx+1][startIdx-1] = newPalindrome
        maxPalindrome = maxPalindrome.length < newPalindrome.length ? 
          newPalindrome: 
          maxPalindrome;
      }
    }
  }
  
  return maxPalindrome;
};

세번쨰 풀이 (통과)


var longestPalindrome = function(s) {
  const dp = Array.from(
    {length: s.length}, 
    (_, i) => Array.from({length: s.length}, (_, j) => (i === j ? s[i] : false)))
  let maxPalindrome = s[0]
  
  s.split('').forEach((c, i) => {
    if(i === s.length - 1) return
    if(c === s[i + 1]) {
      dp[i][i+1] = c + c
      maxPalindrome = c + c
    } 
  })
  
  for (let diff = 0; diff < s.length; diff++) {
    for (let j = 1; j < s.length - diff ; j++) {
      const startIdx = j
      const endIdx = j + diff
      
      const prevChar = s[startIdx - 1]
      const nextChar = s[endIdx + 1]
      if (dp[startIdx][endIdx] && s[startIdx - 1] === s[endIdx + 1]) {
        const newPalindrome = prevChar + dp[startIdx][endIdx] + nextChar
        dp[startIdx-1][endIdx+1] = newPalindrome
        maxPalindrome = maxPalindrome.length < newPalindrome.length ? 
          newPalindrome: 
          maxPalindrome;
      }
    }
  }
  
  return maxPalindrome;
};

효성


var longestPalindrome = function(s) {
    const memo = [...Array(s.length)].map(() => Array(s.length).fill(null));
    for(let len = s.length; len > 0; len--) {
        for(let left = 0; len + left - 1 < s.length; left++ ) {
            const right = left + len - 1;
            if(isPalindrom(s, left, right)) {
                return s.substring(left, right + 1);
            }
        }
    }
       
    function isPalindrom (str, left, right) {
        if(left < 0 || left > s.length || right < 0 || right > s.length) {
            return false;
        }
        if(memo[left][right] !== null) {
            return memo[left][right];
        }
        
        const len = right - left + 1;
        
        if(len <= 2) {
            memo[left][right] = str[left] === str[right];
        }
        else {
            memo[left][right] = str[left] === str[right] && isPalindrom(str, left + 1, right -1);
        }
        return memo[left][right];
    }
};

Longest Palindromic Substring

📄문제

✏️풀이