[leetCode/JS] 5. Longest Palindromic Substring

문제 설명

Given a string s, return the longest palindromic substring in s.
palindromic: A string is palindromic if it reads the same forward and backward.

 

입출력 예

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

 

Example 2:

Input: s = "cbbd"
Output: "bb"

 

Constraints

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

 

---

 

내 솔루션

• i, j 순환하면서 word를 구하고 그 word가 palindromic인지 체크하는 솔루션
• 처음엔 느려서 Time Limit에 걸려서 최적화한다고 고행 좀했다.
• 큰 단어부터 찾기 때문에 그 이하 단어 찾기는 버려도 된다. 처음 찾은 단어가 가장 큰단어가 됨.
• answer length를 slice로 단어를 뽑기전에 길이를 체크하여 check()를 돌리지 않게 한다.

var longestPalindrome = function(s) {
  const check = (str) => {
    if(str.length === 0) return false;
    let palindromic = true;
    for(let i = 0; i < str.length/2; i++){
      if(str[i] !== str[str.length-i-1]){
        palindromic = false;
        break;
      }
    }
    return palindromic;
  }
  let answer = '';
  if(s.length === 1) return s;
  for(let i = s.length + 1; i > 0; i--) {
    for(let j = 0; j < i; j++) {
      if(i - j + 1 > answer.length){
        const word = s.slice(j, i);
        if(check(word)) {
          answer = word;
          break;
        }
      }
    }
  }
  return answer;
};

 

감상평

• 최적화를 어떻게 할지 고민하는 시간이 쫄리면서도 즐거웠다.