[리트코드] 336. Palindrome Pairs / Javascript

문제주소 : https://leetcode.com/problems/palindrome-pairs/

Palindrome Pairs - LeetCode

---

<문제 설명>

Given a list of unique words, return all the pairs of the distinct indices (i, j) in the given list, so that the concatenation of the two words words[i] + words[j] is a palindrome.

 

Example 1:

Input: words = ["abcd","dcba","lls","s","sssll"] Output: [[0,1],[1,0],[3,2],[2,4]] Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: words = ["bat","tab","cat"] Output: [[0,1],[1,0]] Explanation: The palindromes are ["battab","tabbat"]

Example 3:

Input: words = ["a",""] Output: [[0,1],[1,0]]

 

Constraints:

• 1 <= words.length <= 5000
• 0 <= words[i].length <= 300
• words[i] consists of lower-case English letters.

 

<풀이법>

▒ 한줄 개념: 문자열 합친 후 비교 ▒ 

Hard 난이도로 분류되어 있는데, 단순하게 풀어도 해결되는 문제입니다. 

Trie 알고리즘이 정석인 듯 하네요.

저는 단순하게 두 단어끼리 합친 뒤에, 해당 단어가 펠린드롬인지 확인하는 방식으로 풀었습니다.

이후에 다시 풀어봐야할 문제인 것 같습니다.

 

 

<코드(Javascript)>

/**
 * @param {string[]} words
 * @return {number[][]}
 */
var palindromePairs = function(words) {
    const answer = [];
    const l = words.length;
    
    const checkUnion = union => {
        const len = union.length;
        for(let i = 0; i < len/2; i++){
            if(union[i] !== union[len-i-1]){
                return false;
            }
        }
        return true;
    }

    
    for(let i = 0; i < l; i++){
        for(let j = 0; j < l; j++){
            if(i !== j){
                const union = words[i].concat(words[j]);
                if(checkUnion(union)){
                    answer.push([i, j])
                } 
            }
        }
    }
    
    return answer;
};

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest