使用JavaScript的回文索引Hackerrank

Question

我在HackerBank上为回文索引挑战提交了以下代码，但它在一些测试用例中失败，错误为超过时间限制。我不确定我的代码出了什么问题。

基本上，我实现了一个独特的"；"助手"；函数来检查字符串是否为回文。在PalindromeIndex函数中，我首先检查一个字符串是否是回文，然后返回-1，否则我将遍历该字符串，尝试删除每个字母，看看剩下的字符串是否是一个回文。

如果是，则返回索引；否则，继续。

如果循环结束时没有返回任何索引，则意味着没有结果，我返回-1。

这就是我想做的，但我找不到这里的问题。谢谢

function isPalindrome(s) {
for (let i = 0; i < s.length; i++) {
if (s[i] !== s[s.length - 1 - i]) {
return false;
}
}
return true;
}

function palindromeIndex(s) {
let result = isPalindrome(s);
if (result) {
return -1;
}
else {
for (let i = 0; i < s.length; i++) {
let newS = s.slice(0,i) + s.slice(i+1);
if (isPalindrome(newS)) {
return i;
}
}
return -1
}
}

Answer 1

您需要优化回文函数。只需运行从0到数组一半的循环。

function isPalindrome(s) {
for (let i = 0; i < s.length/2; i++) {
if (s[i] !== s[s.length - 1 - i]) {
return false;
}
}
return true;
}

Answer 2

我只起草一个基本想法，因为我想你想自己尝试一下：

aaa = -1   
aaab = 3   
baaa = 0   
bbaa = -1
You only want to loop through the string once.
You only need to loop through half the string, and do comparisons.

我只关注移动指数。

字符串：baaa

默认变量：
位置：-1
startNudge；0
>endNudge：0

在索引i(从0开始(：

• 对照string.length - 1 - i+endNudge检查i+startNudge
• 如果不相等：
  • 对照string.length - 1 - i+endNudge检查索引i + 1+startNudge。
    • 如果相等，则将位置设置为i，并将startNudge设为1
  • 否则，对照string.length - 2 - i+endNudge检查i+startNudge。
    • 如果相等，则将位置设置为string.length - 1 - i，并将endNudge设为-1
  • 否则通过返回-1来中断循环
  • 如果位置已保存，则返回-1以中断循环
• 继续循环

如果循环完成，则返回位置。

Answer 3

。。。否则，我将循环遍历字符串，尝试将每个字母删除到看看剩下的字符串是否是回文

这就是问题所在。没有必要再次遍历整个字符串，因为一旦在字符串中找到一对打破回文的字母，答案必须是该对中第一个字母或第二个字母的索引，或者，如果删除两个字母都没有产生回文，则返回-1。

function palindromeIndex(s) {
function isPalindrome(s) {
for(let i=0; i< Math.floor(s.length/2);i++) {
if(s[i] !== s[s.length-1-i]) {
return false;
}
}
return true;
}
for(let i=0; i< Math.floor(s.length/2); i++) {
if(s[i] !== s[s.length-1-i]) {
if(isPalindrome(s.slice(i, s.length-i-1))) {
return s.length-i-1;  
} else if(isPalindrome(s.slice(i+1,s.length-i))) {
return i;  
} else {
return -1;
}
}
}
return -1;
}
console.log(palindromeIndex('aabaa'))
console.log(palindromeIndex('aaab'))
console.log(palindromeIndex('baaa'))
console.log(palindromeIndex('baaabcc'))

该解决方案的时间复杂度为O(n(，因为只有一个环路是必需的