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 - 是否有可能使我的代碼更快

回答

相關問題