我的代碼有什么問題？有效回文2-Leetcode680

給定一個字串 s，如果從其中洗掉最多一個字符后 s 可以是回文，則回傳 true。

示例 1：

Input: s = "aba"
Output: true

示例 2：

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

示例 3：

Input: s = "abc"
Output: false

對于 leetcode 中的這個問題，我的代碼已經通過了 462/469 個測驗用例：

以下是我的代碼未通過測驗的測驗用例。

"aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"

我的代碼是：

class Solution:
    def validPalindrome(self, s: str) -> bool:
        
        skip=0
        l,r=0,len(s)-1
        
        while l<r:
            if s[l]==s[r]:
                l =1
                r-=1
            elif s[l]!=s[r] and skip<1 and s[l 1]==s[r]:
                l =1
                skip=1
            elif s[l]!=s[r] and skip<1 and s[r-1]==s[l]:
                r-=1
                skip=1
            else:
                return False
        return True

我的代碼有什么問題？

注意：在這個字串中輸出應該是真，我的回傳假

從左邊有字符'lcup'，從右邊有字符'lucup' 我的代碼應該從右側跳過字母u 并繼續。

"aguokepatgbnvfqmgm**lcup**uufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuu**pucul**mgmqfvnbgtapekouga"

另一個例子：它為以下字串回傳 true： s='adau'

按預期跳過字母“u”。

但是，當我根據失敗的測驗用例字串使用示例時，它回傳 False。s= 'cuppucu'

它應該首先從右側跳過 u 并回傳 True 但它沒有。

但是，一旦我用字母“a”替換最后一個字母“u”，它就會跳過字母“a”并回傳 True。這里有什么問題？

uj5u.com熱心網友回復：

我在第一個答案中過于復雜了。我認為您必須多次跳過特定字符。正如其他人指出的那樣，這不是真的。因此，您有其他人的解決方案，但您想知道如何更改代碼以始終做正確的事情。一種方法是運行您的演算法兩次。第一次，您只考慮是否可以跳過輸入字串左側的字符。對于第二個呼叫，您只考慮跳過右側的一個字符。對于像您在這里遇到的情況，您可以選擇跳過任何一個字符，但只有一個會產生積極的結果，那么如果您嘗試兩種情況，一個或另一個總是會在應該成功的時候成功。

所以這是您可以進行的簡單更改...僅稍微修改您的函式，然后呼叫它兩次。

class Solution:

    def _validPalindrome(self, s: str, choose_first: bool) -> bool:
        skip = 0
        l, r = 0, len(s) - 1
        while l < r:
            if s[l] == s[r]:
                l  = 1
                r -= 1
            elif choose_first and s[l] != s[r] and skip < 1 and s[r - 1] == s[l]:
                r -= 1
                skip = 1
            elif not choose_first and s[l] != s[r] and skip < 1 and s[l   1] == s[r]:
                l  = 1
                skip = 1
            else:
                return False
        return True

    def validPalindrome(self, s: str) -> bool:
        return self._validPalindrome(s, False) or self._validPalindrome(s, True)

def main():
    inp = "aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"
    print(Solution().validPalindrome(inp))

main()

結果：

True

這應該適用于您的原始代碼通過的所有情況。

uj5u.com熱心網友回復：

想象一下字串'abbab'。首先，使用值“a”和“b”檢查索引 0 和 4。它們不一樣，但索引 1 處的“b”與索引 4 處的“b”匹配。所以你前進到 1 和 4。接下來是 2 和 3，它們是“b”和“a”，而那些不也不配。故事的結局。

abbab
l   r

abbab
 l  r

abbab
  lr

-> False

現在讓我們切換elif塊。再次首先檢查索引 0 和 4。它們不一樣，所以您現在先更改正確的索引，然后看到 0 和 3 都是“a”。下一個比較是在索引 1 和 2 與“b”。完成的。找到了匹配。

abbab
l   r

abbab
l  r

abbab
 lr

-> True

您沒有要求它，但這是一個采用不同方法的作業解決方案。

class Solution:
    def generate_strings(self, s):
        yield s, s[::-1]
        for pos in range(len(s)):
            t = ''.join(c for i, c in enumerate(s) if i != pos)
            yield t, t[::-1]

    def validPalindrome(self, p):
        return any(x == y for x, y in self.generate_strings(p))

標籤：Python细绳撤销回文

上一篇：將字串轉換為雙精度，但第一個字符是點

下一篇：替換JS中復雜字串中的空格