Approach

• 문자열 s의 길이가 1이라면 그대로 문자열 s를 제출한다. (비교할게 하나의 문자밖에 없기때문)
• 1이 아니라면 이하 코드를 계속 실행.
• 투 포인터를 사용하여 하나의 포인트는 왼쪽에서부터, 즉 index가 i값 부터 차례대로 올라가고 나머지 한 포인터는 오른쪽부터, 즉 index는 문자열의 크기 - 1을 지정해줌으로써 문자열의 끝에서부터 탐색한다.
  • 지정한 포인터 두 개의 문자열 값이 같을 경우 왼쪽 포인터는 인덱스 1을 증가시켜주고 오른쪽 포인터는 인덱스 1을 감소시켜주면서 왼쪽 포인터의 인덱스 값이 오른쪽 포인터의 인덱스 값보다 클때까지 돌려준다.
  • 지정한 포인터 두 개의 문자열 값이 다를 경우 왼쪽 포인터는 기존의 인덱스 i값으로 다시 초기화 시켜주고 처음부터 비교해준다. 오른쪽 포인터는 이전의 인덱스 값에서 -1을 해준 값을 넣어준다.
• 왼쪽 포인터 값이 오른쪽 포인터 값보다 클때 find_str()함수를 통해 i부터 right+left-i, 팰린드롬값이 나온 오른쪽 포인터의 처음 값을 넣어서 문자열을 출력해준다.
• 그렇지 않다면 하나의 문자만 출력한다.

Code

class Solution {
public:
    string find_str(int l, int r, string s)
    {
        string ans ="";
        for(int i = l; i <= r; i++)
        {
            ans += s[i];
        }
        return ans;
    }
    string longestPalindrome(string s) {
        string ans = "";
        int max = 0;
        if(s.length() == 1)
            return s;

        for(int i = 0; i < s.length() -1; i++)
        {
            int left = i, right = s.length()-1;
            while((left <= right))
            {
                if(s[left] != s[right])
                {
                    right+= left-i-1;
                    left = i;
                }
                else
                {
                    left++;
                    right--;
                }
            }
            cout << left << " " << right << "\n";

            if(left > right)
            {
                string str1 = find_str(i, right+left-i, s);
                if(max < str1.length())
                {
                    ans = str1;
                    max = str1.length();
                }
            }
            else 
            {
                ans = s[i];
            }
        }

        return ans;
    }
};

Result

---

추가적인 해결방법

• 문자열의 길이가 1이하이면 그대로 문자열 s를 출력.
• 홀수, 짝수 칸으로 팰린드롬 문자열을 비교한다.
• 1, 2칸으로 시작하여 점점 양쪽으로 퍼져나가며 문자가 다르다면 구한 길이 값을 반환한다.
• 반환된 값을 바탕으로 left(왼쪽 인덱스), right(오른쪽 인덱스) 변수에 저장되어 있는 값과 비교하여 반한된 값이 right-left+1 값보다 클 때 해당 반환된 값의 반을 비교할때 썼던 i값에 대입시켜줌으로써 left, right 값을 갱신시켜준다.

class Solution {
public:
    int GetLength(int l, int r, string str)
    {
        int count = 0;
        while(l >= 0 && r < str.length() && str[l] == str[r])
        {
            l--;
            r++;
            count++;
        }

        if(count == 0) return 0;

        return r-l-1;
    }

    string longestPalindrome(string s) {
        if(s.length() <= 1)
        {
            return s;
        }

        string ans = "";
        int odd_len = 0, even_len = 0, left = 0, right = 0;

        for(int i = 0; i < s.length(); i++)
        {
            odd_len = GetLength(i, i, s);
            even_len = GetLength(i, i+1, s);

            if(odd_len > right-left+1) right = i+(odd_len/2), left = i-(odd_len/2);
            if(even_len > right-left+1) right =  i+(even_len/2), left = i-(even_len/2)+1;
        }

        for(int i = left; i <= right; i++)
        {
            ans += s[i];
        }

        return ans;
    }
};