欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一天一大 lee(回文对)难度:困难-Day20200806

程序员文章站 2022-05-08 11:44:05
...

一天一大 lee(回文对)难度:困难-Day20200806

题目:

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

示例

  1. 示例 1
输入: ["abcd","dcba","lls","s","sssll"]
输出: [[0,1],[1,0],[3,2],[2,4]]
解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
  1. 示例 2
输入: ["bat","tab","cat"]
输出: [[0,1],[1,0]]
解释: 可拼接成的回文串为 ["battab","tabbat"]

抛砖引玉

一天一大 lee(回文对)难度:困难-Day20200806

暴力解法

  • 任取 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
}

枚举前缀和后缀

  • 组成回文的可能情况
    1. a 为 b 到倒序,a+b 刚好组成回文字符
    2. 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(回文对)难度:困难-Day20200806