给定一组唯一的单词, 找出所有不同 的索引对(i, j),使得列表中的两个单词, words[i] + words[j] ,可拼接成回文串。
输入: ["abcd","dcba","lls","s","sssll"]
输出: [[0,1],[1,0],[3,2],[2,4]]
解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
输入: ["bat","tab","cat"]
输出: [[0,1],[1,0]]
解释: 可拼接成的回文串为 ["battab","tabbat"]
抛砖引玉
/**
* @param {string[]} words
* @return {number[][]}
*/
var palindromePairs = function (words) {
let i = 0,
_result = []
while (i < words.length) {
let j = 1
while (j < words.length && i !== j) {
if (check(words[i], words[j])) _result.push([i, j])
if (check(words[j], words[i])) _result.push([j, i])
j++
}
i++
}
// 检验是否为回味字符
function check(a, b) {
if (a.length + b.length === 1) return true
let str = a + b,
left = 0,
right = str.length - 1
while (left < right) {
if (str.charAt(left) === str.charAt(right)) {
left++
right--
} else {
// 对位不相同则返回false
return false
}
}
return true
}
return _result
}
/**
* @param {string[]} words
* @return {number[][]}
*/
var palindromePairs = function (words) {
let n = words.length,
_result = [],
map = new Map()
for (let i = 0; i < n; ++i) {
// 生成倒序字符字符map
const str = words[i].split('').reverse().join('')
map.set(str, i)
}
for (let i = 0; i < n; i++) {
let word = words[i],
m = words[i].length
if (m == 0) continue
for (let j = 0; j <= m; j++) {
// 前缀片段为回文,则验证后缀片段是否存在与之匹配的回文
if (check(word, j, m - 1)) {
let leftId = findWord(word, 0, j - 1)
if (leftId !== -1 && leftId !== i) {
_result.push([i, leftId])
}
}
// 同理,后缀片段为回文,则验证前缀片段是否可以匹配到回文
if (j !== 0 && check(word, 0, j - 1)) {
let rightId = findWord(word, j, m - 1)
if (rightId !== -1 && rightId !== i) {
_result.push([rightId, i])
}
}
}
}
function check(s, left, right) {
let len = right - left + 1
for (let i = 0; i < len / 2; i++) {
if (s.charAt(left + i) !== s.charAt(right - i)) {
return false
}
}
return true
}
function findWord(s, left, right) {
return map.has(s.substring(left, right + 1))
? map.get(s.substring(left, right + 1))
: -1
}
return _result
}
[1]
题目:: https://leetcode-cn.com/problems/palindrome-pair