Palindrome - 是否有可能使我的代码更快

我有一个ASCII字符串，它既可以是回文，也可以通过删除一个字符作为回文。我需要确定它是否已经是回文，如果不是，我需要找到需要删除的字符的索引。例如，如果字符串是'aaba'，那么可以通过删除第一个字符将其制作回文'aba'，因此我需要返回0。Palindrome - 是否有可能使我的代码更快

我有工作代码，但我想知道是否有可能使它更快，因为我需要使用很多长字符串。

这里是我的代码：

package main 

import (
    "fmt" 
    ) 

func Palindrome(s string) bool { 
    var l int = len(s) 

    for i := 0; i < l/2; i++ { 
     if s[i] != s[l - 1 - i] { 
      return false; 
     } 
    } 

    return true 
} 

func RemoveChar(s string, idx int) string { 
    return s[0:idx-1] + s[idx:len(s)] 
} 

func findIdx(s string) int { 
    if Palindrome(s) { 
     return -1 
    } 

    for i := 0; i < len(s); i++ { 
     if Palindrome(RemoveChar(s, i + 1)) { 
      return i 
     } 
    } 

    return -2 
} 

func main() { 
    var s string = "aabaab" 
    fmt.Println(findIdx(s)) 
}

来源

2014-12-13 demas

绝大多数字符串将返回-2，因为您不能通过删除一个字母来使它们成为回文。我首先检查一下你可以明显返回-2但没有更详细的检查的情况 - 例如，如果有超过2个字符出现奇数次，你可以直接返回-2。 – 2014-12-13 06:02:58

您的代码仅适用于ASCII字符。 – peterSO 2014-12-13 06:03:18

@pbabcdefp，我确切地知道有一封信要删除并使其成为回文 – demas 2014-12-13 06:03:56

这里是一个更有效的方法：

func findIdx(s string) int { 
    for i := 0; i < len(s)/2; i++ { 
     if s[i] != s[len(s) - i - 1] { 
      if isPalindrome(s[i+1:len(s)-i]) { 
       return i 
      } else { 
       return len(s) - i - 1 
      } 
     } 
    } 

    return -1 
}

它只是从字符串的两端进行，直到找到一对字节是应匹配，如果字符串是回文，但不。然后它知道它会返回这两个字节之一的索引，所以它只需要执行一个“这是一个回文？”检查;并且它不需要使用RemoveChar函数，因为“这是一个回文？”检查只需要考虑字符串的中间部分（尚未被检查过）。

来源

2014-12-13 06:29:42 ruakh

这应该比ruakh的解决方案稍微高效一些。您不必使用isPalindrome（）来检查s[i + 1:len(s) - i]是回文，因为检查s[i:len(s) - i - 1]是而不是回文更快。在下面的解决方案中，在大多数情况下，j在函数返回之前不会变得很远。

func findIdx(s string) int { 
    var n int = len(s) 
    for i := 0; i < n/2; i++ { 
     if s[i] != s[n - i - 1] { 
      for j := 0; ;j++ { 
       if s[i + j] != s[n - 2 - i - j] { 
        return i; 
       } 
       if s[i + j + 1] != s[n - 1 - i - j] { 
        return n - 1 - i; 
       } 
      } 
     } 
    } 

    return -1 
}

来源

2014-12-13 06:55:50

Palindrome - 是否有可能使我的代码更快

回答

相关问题