一天一大 lee(回文对)难度:困难-Day20200806
程序员文章站
2022-05-08 11:44:05
...
题目:
给定一组唯一的单词, 找出所有不同 的索引对(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"]
抛砖引玉
暴力解法
- 任取 words 中的字符与其他字符拼接验证是否为回文字符
- 注意使用左右边界验证回文时,单个字符也属于回文字符
/**
* @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
}
枚举前缀和后缀
- 组成回文的可能情况
- a 为 b 到倒序,a+b 刚好组成回文字符
- a 或 b 自身存在回文片段,剩余的判断和另外的字符拼接形成完成的回文字符
- 那么讲所有字符划分成前缀后缀组成的字符,验证片段是否为回文,为回文则取查找是否有满足条件的另一半
- 注意:当截取的前缀后缀判断为 0 是,默认为回文字符,则是情况 1,全文平均的回文字符查找
/**
* @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
}
博客: 小书童博客
每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目
欢迎关注留言
公号: 坑人的小书童
下一篇: 成语接龙
推荐阅读
-
一天一大 lee(解数独)难度:困难-Day20200915
-
【一天一大 lee】单词拆分 II (难度:困难) - Day20201101
-
一天一大 lee(冗余连接 II)难度:困难-Day20200917
-
【一天一大 lee】最大间距 (难度:困难) - Day20201126
-
一天一大 lee(N 皇后)难度:困难-Day20200903
-
【一天一大 lee】N皇后 II (难度:困难) - Day20201017
-
【一天一大 lee】插入区间 (难度:困难) - Day20201104
-
一天一大 lee(24点游戏)难度:困难-Day20200822
-
一天一大 lee(回文对)难度:困难-Day20200806
-
一天一大 lee(最短回文串)难度:困难-Day20200829