Algorithm problem-40

1. 문제

• 주어진 문자열의 부분문자열 중 역으로 조회해도 조회 결과가 동일한 문자열의 길이를 리턴
• 즉, 앞 뒤가 똑같은 문자열을 찾는 문제, 공백을 포함한다

2. 시도

• 단순하게 생각해보았음, 모든 부분문자열을 만들어서 저장하고
• 역으로 부분문자열을 만들어 보고, 만들었을 때 부분문자열에 포함되어 있는지를 조회
• 부분문자열에 있다면, 미리 만들어둔 길이를 저장하는 변수와 비교하고 크다면 저장할 것
• 그리고 마지막까지 순회 후, 그 길이를 리턴하면 될듯
• 만들어진 코드는 짧은 문자열이 주어지는 경우에는 작동하는 것을 확인
• 아마 모든 배열을 만들어 저장하는게 문제가 되는 듯(콜스텍 초과)

3. 수도코드

let longestPalindrome = function (str) {
  // 길이값을 저장할 변수를 선언
  let palLen = 0;
  // 문자열의 길이가 1 이하인 경우는 그대로 리턴
  if (str.length <= 1) return str.length;
  // 부분문자열을 만들어서 저장할 배열을 선언
  let subStr = [];
  // 이 부분이 계산 범위를 넘어가는 듯(콜스텍 초과)
  // 짧은 문장의 경우는 계산이 잘 되는 것은 확인
  // 반복문으로 부분문자열을 모두 저장한다
  for (let i = 0; i < str.length; i++) {
    let curStr = '';
    curStr = curStr + str[i];
    subStr.push(curStr);
    for (let j = i + 1; j < str.length; j++) {
      curStr = curStr + str[j];
      subStr.push(curStr);
    }
  }
  // 반복문으로 역순의 부분문자열을 만들고, 만든 문자열이 배열에 있는지 체크
  // 배열에 있다면, 그 길이가 저장한 길이값보다 길다면 갱신하도록
  for (let k = str.length - 1; k >= 0; k--) {
    let revStr = '';
    revStr = revStr + str[k];
    if (subStr.includes(revStr) && revStr.length > palLen) {
      palLen = revStr.length;
    }
    for (let l = k - 1; l >= 0; l--) {
      revStr = revStr + str[l];
      if (subStr.includes(revStr) && revStr.length > palLen) {
        palLen = revStr.length;
      }
    }
  }
  return palLen;
};

4. 레퍼런스