[Leetcode] 5. Longest Palindromic Substring

---

Given a string s, return the longest palindromic substring in s.

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.

일단 C++을 너무 몰라서 string stl 부터 보자!

string 초기화 방법 ) 

 string str;
 // 빈 문자열 str 생성
 
 string str = "abcdef";
 string str;
 str = "abcdef";
 // "abcdef" 로 선언된 str 생성

 string str("abcdef");
 // "abcdef" 로 선언된 str 생성

 string str2(str1);
 // str1 문자열을 복사한 str2 생성

 char s[ ] = {'a', 'b', 'c', 'd', 'e', 'f'};
 string str(s);
 //C에서의 문자열과 호환 가능

 string *str = new string("abcdef");
 //new를 이용한 동적할당

출처: https://rebro.kr/53 [Rebro의 코딩 일기장:티스토리]

- 문자열 비교 (<, >, ==) : 두 문자열의 사전 순서를 비교, 또는 동일 여부를 확인할 수 있다. 

- 문자열 연결 (+) : 두 문자열을 이어주는 역할을 한다. 

search할때는 아래와 같이 쓸 수 있다

 str.find("abcd")
"abcd"가 str에 포함되어있는지를 확인. 찾으면 해당 부분의 첫번째 index를 반환

 str.find("abcd", n)
n번째 index부터 "abcd"를 find

brute-force로 하면 문자열 비교로 해야할 것 같고, 좀 더 효율적인 알고리즘이 있을 것 같은데...

일단 마냥 substr의 경우의 수를 다 해서 brute-force로 해보려니 역시나 Compile error

아래와같이 i 는 index, j는 substring의 길이로 해서 max_l 즉 지금까지 제일 길었던 것으로 하게끔 수정해서 했으나... Time limit이 떴다.

class Solution {
public:
    bool isPalindrom(string s, int len){
        for(int i=0;i<len/2;i++){
            if(s[i]!=s[len-i-1]) return false;
        }
        return true;
    }

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

        string ret=s.substr(0,1);
        int max_l = 1;

        for(int i=0;i<l;i++){
            for(int j=i+max_l;j<=l;j++){
                if(isPalindrom(s.substr(i, j-i), j-i))
                {
                    if(max_l < (j-i)){
                        max_l = j-i;
                        ret = s.substr(i, j-i);
                    }
                }
            }
        }
        return ret;
    }
};

Solution : Expand Around Center

주어진 string의 모든 panlindromic substring을 찾기 위해선, 먼저 palindrome의 시작가능한 모든 곳을 늘려가며 찾고, 끝나는 모든 곳을 늘려가며 찾으면된다.

그 말인 즉슨, palindrome은 중간문자를 사이로 양쪽이 대칭이므로, palindrome은 중간문자를 기준으로부터 늘려(확장)시켜나갈 수 있고, 2n-1개의 중간지점이 있을 수 있다.

여기서 왜 n개가 아니고 2n-1개냐?! 그것은 두 문자 사이에 palindrome의 중간이 있을 수 있어서...예를 들어, abba와 같이 짝수개의 문자로 이루어지면 중간문자는 두 b 사이가 되기 때문. 이렇게 확장시켜나감에 따라 시간복잡도는 O(n)이 되게된다. (전체적으로는 O(n^2))

알고리즘

1. maz_str = s[0] , max_len = 1 로 시작한다 (모든 한 글자는 palindrome이니까)
2. 자, 이제 string을 순회하고 모든 문자에 대해 center 중간문자로 두고 확장시켜나가면된다
3. 홀수 길이의 palindrome의 경우, 현재 문자를 중간문자로 잡고 확장시키고
4. 짝수 길이의 palindrome의 경우, 현재 문자와 옆문자를 중간문자로 잡고 확장시켜나간다
5. 최대길이의 substring을 찾아내고 이를 출력

Code

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        if(len<=1) return s;

        auto expand_from_center = [&](int left, int right) {
            while (left >= 0 && right < len && s[left] == s[right]) {
                left--;
                right++;
            }
            return s.substr(left + 1, right - left - 1);
        };

        string max_str = s.substr(0, 1);
        for (int i = 0; i < len - 1; i++) {
            string odd = expand_from_center(i, i);
            string even = expand_from_center(i, i + 1);

            if (odd.length() > max_str.length()) {
                max_str = odd;
            }
            if (even.length() > max_str.length()) {
                max_str = even;
            }
        }

        return max_str;
    }
};

후.. 어떻게 이런 생각을 하지

일단 C++ auto 부터 공부해야겠다.