题目链接：https://leetcode-cn.com/problems/palindrome-pairs/
参考链接：
https://leetcode-cn.com/problems/house-robber-iii/solution/da-jia-jie-she-iii-by-leetcode-solution/
给定一组唯一的单词， 找出所有*不同* 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
示例 1:
输入: ["abcd","dcba","lls","s","sssll"]
输出: [[0,1],[1,0],[3,2],[2,4]]
解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2:
输入: ["bat","tab","cat"]
输出: [[0,1],[1,0]]
解释: 可拼接成的回文串为 ["battab","tabbat"]
- 万万没想到，暴力也能过
- 就是简单的两两拼接，然后判断是否是回文
/**
* @param {string[]} words
* @return {number[][]}
*/
var palindromePairs = function(words) {
let res = []
for(let i = 0, l = words.length; i < l; i++){
for(let j = 0; j < l; j++){
if(i === j){
continue
}
if(isPalindrome(words[i]+words[j])){
res.push([i, j])
}
}
}
return res
};
var isPalindrome = function(string) {
let left = 0;
let right = string.length-1;
while(left<right){
if(string[left]!==string[right]){
return false
}
left++;
right--
}
return true
};- 假设两个字符串
s1和s2可以拼接成一个回文字符串，则会有以下两种情况s1.length === s2.length，说明s1是s2的反转s1.length > s2.length或者s1.length < s2.length，说明两者中长度大字符串可以分为两部分，一部分为回文字符串，另一部分为短字符串的反转
- 所以遍历字符串，对每个字符串再进行遍历，找到回文字符，判断剩余字符是否在数组中有匹配
- 使用map存储每个字符串的反转，进行匹配
- 使用set存放回文对索引，进行去重
/**
* @param {string[]} words
* @return {number[][]}
*/
var palindromePairs = function (words) {
// 用Map存每个字符串的翻转
const map = new Map()
// 用Set存回文对的索引，以避免重复
const set = new Set()
// map的key为字符串的翻转，value为字符串的索引
words.forEach((word, i) => {
map.set(word.split('').reverse().join(''), i)
})
for (let i = 0; i < words.length; i++) {
const word = words[i]
for (let j = 0; j <= word.length; j++) {
// 将字符串分为左右两个字串
const left = word.slice(0, j), right = word.slice(j)
// 如果左字符串是回文的
if (isPalindrom(left)) {
// 如果map里存有右字符串且索引不是i（题目写着要不同的索引对）
if (map.has(right) && map.get(right) !== i) {
// 满足前面条件的字符串为 右字符串的翻转 + 本身是回文的左字符串 + 右字符串
// 这是一个回文字符串，其索引对为[map.get(right),i]
// 因为数组没办法去重，所以用字符串表示并存入set
const temp = `${map.get(right)},${i}`
set.add(temp)
}
}
// 如果右字符串是回文的
if (isPalindrom(right)) {
// 如果map里存有左字符串且索引不是i（题目写着要不同的索引对）
if (map.has(left) && map.get(left) !== i) {
// 满足前面条件的字符串为 左字符串 + 本身是回文的右字符串 + 左字符串的翻转
const temp = `${i},${map.get(left)}`
set.add(temp)
}
}
}
}
// 将set中表示索引对的字符串转化为数组存到ans里
const ans = [...set].map(v => v.split(','))
return ans
}
// 判断是否是回文字符串
function isPalindrom(str) {
let i = 0, j = str.length - 1
while (i < j) {
if (str[i] !== str[j]) {
return false
}
i++
j--
}
return true
}- 与思路2相同，但是使用字典树的方式缓存每个反转
- 字典树又称单词查找树、前缀树，是一种树形结构，利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，比哈希表更快。
- 基本性质
- 根节点不包含字符，除根节点外每个节点都只包含一个字符；
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
- 每个节点的所有子节点包含的字符都不相同。
- 将每一个字符串插入字典树中，
tree[add].chi[i]保存着数字即意味着当前字母存在于字典树中第几个节点中，所以add = tree[add].chi[i]；同时，如果字母是'a'，那么i为0，字母是'b'，i为1，以此类推，需要使用到charCodeAt()转换为ascii码。
/**
* @param {string[]} words
* @return {number[][]}
*/
//主程序
var palindromePairs = function(words) {
//创建字典树中的节点对象
function createNode() {
var obj = {};
obj.chi = new Array(26).fill(0);
obj.flag = -1;
return obj;
};
var tree = new Array();
tree.push(createNode());
var n = words.length;
for(let i = 0; i < n; i++) {
insert(words[i], i); //将字符串数组中的所有字符串先加入字典树
};
var ret = new Array();
for(let i = 0; i < n; i++) {
var m = words[i].length;
for(let j = 0; j <= m; j++) {
if(isPalindrome(words[i], j, m - 1)) { //如果字符串i的j至m-1位为回文串
var leftId = findWord(words[i], 0, j - 1); //需要在字典树中寻找是否存在字符串i倒序的字符串
if (leftId != -1 && leftId != i) {
ret.push([i, leftId]);
}
}
if(j !=0 && isPalindrome(words[i], 0, j - 1)) {
var rightId = findWord(words[i], j, m - 1);
if(rightId != -1 && rightId != i) {
ret.push([rightId, i]);
}
}
}
};
return ret;
//将每一个字符串插入到字典树当中
function insert(s, id) {
var len = s.length, add = 0;
for(let i = 0; i < len; i++) {
var x = s[i].charCodeAt() - 'a'.charCodeAt();
if(tree[add].chi[x] == 0) {
tree.push(createNode());
tree[add].chi[x] = tree.length - 1;
}
//tree[add].ch[x]保存着子节点在tree中的位置；同时，不等于0说明当前字母与节点所代表的字母相等
add = tree[add].chi[x];
}
tree[add].flag = id; //标记下标为add的节点保存了第id个字符串
}
//判断字符串是否为回文
function isPalindrome(s, left, right) {
var len = right - left + 1;
for(let i = 0; i < len / 2; i++) {
if(s[left + i] != s[right - i]) {
return false;
}
}
return true;
}
//在字典树中寻找判断是否存在某字符串的倒序
function findWord(s, left, right) {w
var add = 0;
for(let i = right; i >= left; i--) {
var x = s[i].charCodeAt() - 'a'.charCodeAt();
if(tree[add].chi[x] == 0) {
return -1;
}
add = tree[add].chi[x];
}
return tree[add].flag; //节点的flag在insert函数中保存了字符串在字符串数组中的下标
}
};- 字典树是查询相同前缀或者后缀的好办法