<Hard> Palindrome Pairs (LeetCode : C#)

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

📕 문제 설명

unique한 문자열 배열 words가 주어질 때 palindrome pair 반환하기

palindrome pair이란?
(i, j)
1) 0 <= i, j < words.length
2) i != j
3) words[i] + words[j] = palindrome

• Input
  unique한 문자열 배열 words
• Output
  words의 palindrome pair 배열

예제

시도 1.

완전탐색

public class Solution {
    public IList<IList<int>> PalindromePairs(string[] words) {
        List<IList<int>> answerList = new List<IList<int>>();
        for (int i = 0; i < words.Length; i++)
        {
            for (int j = i + 1; j < words.Length; j++)
            {
                string currentWord = words[i] + words[j];

                if (IsPalindrome(currentWord))
                {
                    answerList.Add(new List<int>() {i, j});
                }

                string reverseWord = words[j] + words[i];
                if (IsPalindrome(reverseWord))
                {
                    answerList.Add(new List<int>() {j, i});
                }
            }
        }

        return answerList;
        
    }

    public bool IsPalindrome(string s)
    {
        int i = 0;
        int j = s.Length - 1;
        while (i < j)
        {
            if (s[i++] != s[j--]) return false;    
        }

        return true;
    }
}

풀이

public class Solution {
    public IList<IList<int>> PalindromePairs(string[] words)
    {
        List<IList<int>> answerList = new();
        Dictionary<string, int> dict = new Dictionary<string, int>();
        for (int i = 0; i < words.Length; i++)
        {
            dict.Add(words[i], i);
        }

        foreach (var (word, i) in dict)
        {
            int j = 0;
            string r = string.Concat(word.Reverse());

            // case1: abcd, dcba (글자수 같고 뒤집은게 일치하는 경우)
            if (dict.TryGetValue(r, out j) && j != i) // 거꾸로 뒤집은게 있으면 바로 answer에 추가 
            {
                answerList.Add(new List<int>{ i, j });
            }
                

            for (int k = 0; k < word.Length; k++)
            {
                // case2:  xyzll + xyz
                // reverse: llzyx -> ll이 palindrome, zyx reverse인 xyz 존재
                // 앞이 palindrome 이고, 그 뒤에 자른 부분에 대해 reverse가 존재한다면 answer 가능 
                if (IsPalindrome(r.Substring(0, word.Length-k)) && dict.TryGetValue(r.Substring(word.Length-k), out j)) 
                {
                    answerList.Add(new List<int>{ i, j }); // i먼저!
                } 
                
                // case3: zyx + llxyz
                // reverse: zyxll -> zyx reverse 존재 + ll palindrome 
                // k번 이후부터 palindrome + 0~k까지 reverse 존재 
                if (IsPalindrome(r.Substring(k)) && dict.TryGetValue(r.Substring(0,k), out j)) 
                {
                    answerList.Add(new List<int>{ j, i }); // j먼저!
                }
            }
        }

        return answerList;
    }

    private bool IsPalindrome(string s)
    {
        int i = 0;
        int j = s.Length - 1;
        while (i < j)
        {
            if (s[i++] != s[j--]) return false;    
        }

        return true;
    }
}

결과