<Hard> Shortest Palindrome (LeetCode : C#)

https://leetcode.com/problems/shortest-palindrome/

📕 문제 설명

문자열이 주어질 때 제일 앞에 문자들을 추가해서 변환 후 가장 짧은 palindrome 반환하기

palindrome: 앞 뒤로 뒤집어도 같은 단어 (ex - aba, 토마토 .. )

• Input
  문자열
• Output
  변환 후 가장 짧은 palindrome

예제

풀이

1) 주어진 문자열 첫 문자 부터 전체 길이 보기 전까지 palindrome인지 확인하기 (palindrome이면 그때의 index 기록)
2) 첫 문자에서 시작했을 때 제일 긴 palindrome 찾으면 그 때의 index부터 뒷 부분 문자 가져오기
3) 뒷 부분 문자 뒤집은거랑 주어진 문자열 더해서 반환하기

public class Solution {
    public string ShortestPalindrome(string s) {
        int currPalindromeIndex = -1;
        // 제일 처음 값을 기준으로 substring하면서 palindrome인지 판단
        // 처음 기준 최대 길이의 palindrome 뒤의 index 부분부터 가져와서 reverse 해서 앞에 붙이면 됨
        for (int i = 1; i <= s.Length; i++)
        {
            if ((i % 2 != 0) && IsOddPalindrome(s.Substring(0, i))) 
            {
                currPalindromeIndex = i - 1;
            }
            if ((i % 2) == 0 && IsEvenPalindrome(s.Substring(0, i)))
            {
                currPalindromeIndex = i - 1;
            }
        }

        if (currPalindromeIndex == s.Length - 1) return s;
        string stringToAdd = s.Substring(currPalindromeIndex + 1, s.Length - currPalindromeIndex - 1);

        char[] charArray = stringToAdd.ToCharArray();
        Array.Reverse(charArray);

        return new string(charArray) + s;
    }

    public bool IsOddPalindrome(string s) // 홀수일 때 palindrome 구하기
    {
        int mid = s.Length / 2;
        int lp = mid - 1;
        int rp = mid + 1;

        while(lp >= 0 && rp < s.Length)
        {
            if (s[lp] != s[rp]) return false;
            lp -= 1;
            rp += 1;
        }

        return true;
    }
    
    public bool IsEvenPalindrome(string s) // 짝수일 때 palindrome 구하기
    {
        int mid1 = s.Length / 2 - 1;
        int mid2 = s.Length / 2;

        if (s[mid1] != s[mid2]) return false;

        int lp = mid1 - 1;
        int rp = mid2 + 1;
        while (lp >= 0 && rp < s.Length)
        {
            if (s[lp] != s[rp]) return false;
            lp -= 1;
            rp += 1;
        }

        return true;
    }
}

결과