挑战回文索引
登录
标签搜索
侧边栏壁纸
博主昵称
Flying

  • 累计撰写 267 篇文章
  • 累计收到 2 条评论
JavaScript

挑战回文索引

Flying
Flying
2023-12-23 / 0 评论 / 71 阅读 / 正在检测是否收录...

palindrome.svg

问题

让我们将这个挑战拆分为需求：

  • 挑战链接：HackerRank 回文索引代码挑战
  • 你将收到一个字符串，s
  • s 的长度在1到100005之间（包括1和100005）
  • 你被允许删除一个字母
  • 如果删除一个字母，必须返回它的索引
  • 删除字母后的字符串将等于其反向字符串（即回文）
  • 如果不需要删除任何字符串，或需要删除多于一个字符的字符串，则返回 -1
// 例子
"ababab"
// 结果
5
// 原因：删除索引 5 处的字母
"ababa" = "ababa" 的反向

目标
编写一个函数或多个函数，返回从字符串（s）中删除的字母的索引，以使其成为回文，如果不可能或未删除任何字符串，则返回 -1。

覆盖我们的基础

确保我们满足要求：

function palindromeIndex(s) {
  let result = -1;
  const slen = s.length;

  if (slen >= 1 && slen <= 100005) {
    // 继续代码
  }

  return result;
}

我们还需要考虑字符串本身翻转后是否需要删除任何字符才能使其成为回文。

function palindromeIndex(s) {
  let result = -1;
  const slen = s.length;

  if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
    // 继续代码
  }

  return result;
}

理解问题

当我第一次尝试解决这个问题时，我想出了一个快速解决方案，然后重构了一些内容，使其更加高效。HackerRank 不仅会评估你的答案是否正确，还会评估你的代码是否在时间限制内运行，或者它是否会给出错误并超时。我将首先演示我的第一次尝试，然后展示我是如何进行优化的。

阅读问题时，我知道为了比较字符串和它的反向字符串，我需要使用循环遍历它。基本上，一次移除一个字符，比较字符串和它的反向字符串，然后要么返回解决方案，要么继续。

遍历字符

我们绝对需要使用 for 循环遍历字符：

function palindromeIndex(s) {
  let result = -1;
  const slen = s.length;

  if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {

    for (let i = 0; i < slen; i++) {
      // 继续代码
    } 
  }

  return result;
}

创建新字符串

接下来，我们需要创建一个新字符串，其中移除了索引 i 处的字符，创建其反向字符串并比较字符串。注意这是一个 for 循环，一旦找到答案，我们可以通过在循环中添加 break 来进行一些优化，无需继续循环。

function palindromeIndex(s) {
  let result = -1;
  const slen = s.length;

  if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {

    for (let i = 0; i < slen; i++) {

      // 创建新字符串
      let newS = s.substring(0, i) + s.substring((i + 1)); 

      // 创建该字符串的反向字符串
      let revNewS = newS.split('').reverse().join('');

      // 比较
      if (newS === revNewS) {
        result = i;
        break; 
      }
    } 
  }

  return result;
}

第一种解决方案存在的问题

当我运行测试时，大多数初始较小的值都返回了正确的结果。问题出在s的长度为 73785 或更长时。结果返回：
由于超时而终止

重新理解问题

要了解如何解决这个问题，我们需要理解我们正在比较什么？我们正在比较一个字符串和它的反向字符串。然后我们可以假设我们正在尝试实现的结果是确保它是一个回文，或者只是验证一个现有的回文。这使我们理解，我们可以假设s已经是一个回文，我们只是要确保它符合回文的要求。

回文的要求

回文的要求是它从前到后读和从后到前读是相同的。这意味着第一个字母等于最后一个字母，第二个字母等于倒数第二个字母，依此类推。通过这种理解，我们基本上只是在比较字母，确保它们相同。

// 例子 - "acbba"↓       ↓
a c b b a = ✅相同 
  ↓   ↓
a c b b a = 🚫不相同

比较字母

重构我们原始的 for 循环解决方案如下：

function palindromeIndex(s) {
     let result = -1;
     const slen = s.length; 
     
     if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
           
          for (let i = 0; i < slen; i++) {
               
               // 比较第一个字母与最后一个字母，依此类推
               if (s.charAt(i) != s.charAt(len - 1 - i)) {
               } 
          } 
     }
      
     return result;
}

决定删除哪个字母

一旦我们发现两个字母都不相等，我们就需要决定是在开头删除字母还是在结尾删除字母。

// 带有 for 循环的例子 - "acbba"
... 
i = 1
  ↓   ↓
a c b b a = 🚫不相同// 预期答案应该是 i (1)// 带有 for 循环的例子 - "abbca"
... 
i = 1
  ↓   ↓
a b b c a = 🚫不相同// 预期答案应该是 3 或 (length - 1 - i)

然后，我们需要评估两种情况来找到我们的答案。

function palindromeIndex (s) {
    let result = -1;
    const slen = s.length; 
    
    if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {

      for (let i = 0; i < slen; i++) {
            
        // 比较第一个字母与最后一个字母，依此类推
        if (s.charAt(i) != s.charAt(slen - 1 - i)) {

          // 考虑在开头的字母
          let s1 = s.substring(0, i) + s.substring((i + 1)); 
          // 考虑在结尾的字母
          let s2 = s.substring(0, (slen - 1 - i)) + s.substring((len - 1 - i) + 1); 
        } 
      } 
    }
    
    return result;
}

比较字符串

在获得了两个字符串之后，我们需要将它们与它们的反向版本进行比较，并返回相应的结果。请注意，我们仍然在 for 循环中，因此一旦我们得到答案，我们可以使用 break 来跳过比较的 for 循环的其余部分。

function palindromeIndex(s) {
  let result = -1;
  const slen = s.length; 

  if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {

    for (let i = 0; i < slen; i++) {

      // 比较第一个字母与最后一个字母，依此类推
      if (s.charAt(i) != s.charAt(slen - 1 - i)) {

        // 考虑在开头的字母
        let s1 = s.substring(0, i) + s.substring((i + 1)); 
        // 考虑在结尾的字母
        let s2 = s.substring(0, (slen - 1 - i)) + s.substring((len - 1 - i) + 1); 

        if (s1 === s1.split('').reverse().join('')) {
          result = i;
          break; 
        } else if (s2 === s2.split('').reverse().join('')) {
          result = slen - 1 - i;
          break;
        }  
      } 
    } 
  }

  return result;
}

已经开始看起来不错，但我们需要考虑另一种用例。

多个字母的情况怎么办

考虑有多个字母需要被替换的情况。根据要求，我们只能删除一个字母。因此，我们可以假设如果需要删除多个字母，则返回 -1。这是我们可以添加最后一个 else 来处理这种情况。

// 例子情境 - "acbdbba"... 
i = 1
↓       ↓
a c b d b b a = 🚫不相同// 如果我们移除 c
"abdbba" != "abbdba"// 如果我们移除 b
"acbdba" != "abdbca"// 为了使它成为回文，我们需要删除另一个字母
// 这超出了我们的要求，因此结果 = -1

我们的代码将像下面这样加入最后一个 else：

function palindromeIndex (s) {
  let result = -1;
  const slen = s.length; 

  if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {

    for (let i = 0; i < slen; i++) {

      // 比较第一个字母与最后一个字母，依此类推
      if (s.charAt(i) != s.charAt(slen - 1 - i)) {

        // 考虑在开头的字母
        let s1 = s.substring(0, i) + s.substring((i + 1)); 
        // 考虑在结尾的字母 
        let s2 = s.substring(0, (slen - 1 - i)) + s.substring((len - 1 - i) + 1); 

        if (s1 === s1.split('').reverse().join('')) {
          result = i;
          break; 
        } else if (s2 === s2.split('').reverse().join('')) {
          result = slen - 1 - i;
          break;
        } else { 
          // 顶部已经假定 result = -1
          break;
        } 
      } 
    } 
  }

  return result;
}

进一步优化代码

我们可以进行两个最后的优化。

  • 优化多个断点
function palindromeIndex (s) {
  let result = -1;
  const slen = s.length; 

  if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {

    for (let i = 0; i < slen; i++) {

      // 比较第一个字母与最后一个字母，依此类推
      if (s.charAt(i) != s.charAt(slen - 1 - i)) {

        // 考虑在开头的字母
        let s1 = s.substring(0, i) + s.substring((i + 1)); 
        // 考虑在结尾的字母 
        let s2 = s.substring(0, (slen - 1 - i)) + s.substring((len - 1 - i) + 1); 

        if (s1 === s1.split('').reverse().join('')) {
          result = i;
        } else if (s2 === s2.split('').reverse().join('')) {
          result = slen - 1 - i;
        } 
        // else 已经假定 
        // 并且假定有一个 break 
        // 还考虑了 result = -1
        break;
      } 
    } 
  }

  return result;
}
  • 优化 For 循环

尽管这不是必要的，因为有了 break，我们还可以假设我们不需要遍历整个字符串，只需要一半，因为我们假设字符串是相同的。然后我们可以将 for 循环长度减半：

function palindromeIndex (s) {
  let result = -1;
  const slen = s.length; 

  if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {

    for (let i = 0; i < slen / 2; i++) {

      // 比较第一个字母与最后一个字母，依此类推
      if (s.charAt(i) != s.charAt(slen - 1 - i)) {

        // 考虑在开头的字母
        let s1 = s.substring(0, i) + s.substring((i + 1)); 
        // 考虑在结尾的字母 
        let s2 = s.substring(0, (slen - 1 - i)) + s.substring((len - 1 - i) + 1); 

        if (s1 === s1.split('').reverse().join('')) {
          result = i;
        } else if (s2 === s2.split('').reverse().join('')) {
          result = slen - 1 - i;
        } 
        // else 已经假定 
        // 并且假定有一个 break 
        // 还考虑了 result = -1
        break;
      } 
    } 
  }

  return result;
}

虽然不是必需的，但如果我们决定因此移除一个以上的字符，这可能会有所帮助。

解决方案

不带注释的完整解决方案：

function palindromeIndex (s) {
  let result = -1;
  const slen = s.length; 

  if (slen >= 1 && slen <= 100005 & s !== s.split('').reverse().join('')) {
    for (let i = 0; i < slen; i++) {
      if (s.charAt(i) != s.charAt(slen - 1 - i)) {
        let s1 = s.substring(0, i) + s.substring((i + 1)); 
        let s2 = s.substring(0, (slen - 1 - i)) + s.substring((len - 1 - i) + 1); 

        if (s1 === s1.split('').reverse().join('')) {
          result = i;
        } else if (s2 === s2.split('').reverse().join('')) {
          result = slen - 1 - i;
        }                              


        break;
      } 
    } 
  }

  return result;
}

测试用例

现在让我们验证代码：

palindromeIndex("a"); // -1 ✅
palindromeIndex(""); // -1 ✅
palindromeIndex("acbdbba"); // -1 ✅
palindromeIndex("aaab"); // 3 ✅
palindromeIndex("acbba"); // 1 ✅

链接

1
优化算法
版权属于： Flying
本文链接： https://51fe.site/challenge-palindrome-index.html
作品采用： 《 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 》许可协议授权
相关推荐
JavaScript 位运算符
JavaScript 位运算符
 查找最长公共子序列
查找最长公共子序列
 使用余数运算符改进算法
使用余数运算符改进算法
 React Native 性能优化
React Native 性能优化

评论 (0)

取消