336. Palindrome Pairs

[Tcdian]

336. Palindrome Pairs

给定一组 唯一 的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

Example 1

Input: ["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: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]

[Tcdian]

Solution ( 暴力解法 )

• JavaScript Solution

/**
 * @param {string[]} words
 * @return {number[][]}
 */
var palindromePairs = function(words) {
    const reuslt = [];
    for (let i = 0; i < words.length; i++) {
        for (let j = 0; j < words.length; j++) {
            if (i === j) {
                continue;
            }
            if (isPalindrome(`${words[i]}${words[j]}`)) {
                reuslt.push([i, j]);
            }
        }
    }
    return reuslt;
};

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

• TypeScript Solution

function palindromePairs(words: string[]): number[][] {
    const reuslt: number[][] = [];
    for (let i = 0; i < words.length; i++) {
        for (let j = 0; j < words.length; j++) {
            if (i === j) {
                continue;
            }
            if (isPalindrome(`${words[i]}${words[j]}`)) {
                reuslt.push([i, j]);
            }
        }
    }
    return reuslt;
};

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