[LeetCode] 336. Palindrome Pairs

😎풀이

1. 단어의 역순을 미리 저장
2. 단어를 순회하며 다음 케이스를 탐색
   2-1. 공백과 현재 단어를 조합하여 팰린드롬을 만들 수 있는 경우
   2-2. 현재 단어가 단어 사전에 있는 경우 (단어 사전은 역순으로 저장되어 있으므로 알맞는 짝이 있음)
   2-3. 현재 단어의 일부가 팰린드롬이며, 나머지가 단어 사전에 있는 경우
3. 짝이 맞는 팰린드롬들의 인덱스 반환

function palindromePairs(words: string[]): number[][] {
    const result = []
    const wordMap = new Map<string, number>()
    for(let i = 0; i < words.length; i++) wordMap.set(words[i].split('').reverse().join(''), i)
    for(let i = 0; i < words.length; i++) {
        const word = words[i]
        if(wordMap.has('') && word !== '' && isPalindrome(word)) {
            const emptyIdx = wordMap.get('')
            result.push([i, emptyIdx])
            result.push([emptyIdx, i])
        }
        if(wordMap.has(word) && wordMap.get(word) !== i) {
            result.push([i, wordMap.get(word)])
        }
        for(let j = 1; j < word.length; j++) {
            const left = word.slice(0, j)
            const right = word.slice(j)
            if(isPalindrome(left) && wordMap.has(right)) {
                result.push([wordMap.get(right), i])
            }
            if(isPalindrome(right) && wordMap.has(left)) {
                result.push([i, wordMap.get(left)])
            }
        }
    }
    return result
};

function isPalindrome(word: string) {
    let left = 0
    let right = word.length - 1
    while(left < right) {
        if(word[left] !== word[right]) return false
        left++
        right--
    }
    return true
}