leetcode 1616. Split Two Strings to Make Palindrome (python)

語言: CN / TW / HK

「這是我參與11月更文挑戰的第27天,活動詳情檢視:2021最後一次更文挑戰

描述

You are given two strings a and b of the same length. Choose an index and split both strings at the same index, splitting a into two strings: aprefix and asuffix where a = aprefix + asuffix, and splitting b into two strings: bprefix and bsuffix where b = bprefix + bsuffix. Check if aprefix + bsuffix or bprefix + asuffix forms a palindrome.

When you split a string s into sprefix and ssuffix, either ssuffix or sprefix is allowed to be empty. For example, if s = "abc", then "" + "abc", "a" + "bc", "ab" + "c" , and "abc" + "" are valid splits.

Return true if it is possible to form a palindrome string, otherwise return false.

Notice that x + y denotes the concatenation of strings x and y.

Example 1:

  • Input: a = "x", b = "y"
  • Output: true
  • Explaination: If either a or b are palindromes the answer is true since you can split in the following way:
  • aprefix = "", asuffix = "x"
  • bprefix = "", bsuffix = "y"
  • Then, aprefix + bsuffix = "" + "y" = "y", which is a palindrome.

Example 2:

  • Input: a = "abdef", b = "fecab"
  • Output: true

Example 3:

  • Input: a = "ulacfd", b = "jizalu"
  • Output: true
  • Explaination: Split them at index 3:
  • aprefix = "ula", asuffix = "cfd"
  • bprefix = "jiz", bsuffix = "alu"
  • Then, aprefix + bsuffix = "ula" + "alu" = "ulaalu", which is a palindrome.

Example 4:

  • Input: a = "xbdef", b = "xecab"
  • Output: false

Note:

1 <= a.length, b.length <= 10^5
a.length == b.length
a and b consist of lowercase English letters

解析

根據題意,給定兩個長度相同的字串 a 和 b。 選擇一個索引並在同一索引處拆分兩個字串,將 a 拆分為兩個字串:aprefix 和 asuffix,其中 a = aprefix + asuffix,將 b 拆分為兩個字串:bprefix 和 bsuffix,其中 b = bprefix + bsuffix。 檢查 aprefix + bsuffix 或 bprefix + asuffix 是否形成迴文。

將字串 s 拆分為 sprefix 和 ssuffix 時,允許 ssuffix 或 sprefix 為空。 例如,如果 s = "abc",則 "" + "abc"、"a" + "bc"、"ab" + "c" 和 "abc" + "" 是有效的拆分。如果可以形成迴文字串則返回 True ,否則返回 False。請注意,x + y 表示字串 x 和 y 的串聯。

其實這道題使用貪心的思想還是比較容易的,加入我們有兩個字串 a 和 b ,並且用中線假定劃分的位置,如下:

  • a:AB | CD | EF
  • b:GH | KJ | LM

如果 a 的字首和 b 的字尾能組成迴文,那麼 AB 一定和 LM 能組成迴文,那麼只需要判斷並且 CD 或者 KJ 是否是迴文即可,即:AB+CD+LM 或者 AB+KJ+LM 這兩種情況可以組成迴文。將 b 的字首和 a 的字尾組成迴文也是相同的邏輯。

解答

class Solution(object):
    def checkPalindromeFormation(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: bool
        """
        return self.check(a, b) or self.check(b,a)

    def check(self, a, b):
        if len(a) == 1 : return True
        i = 0
        j = len(a) - 1
        while i<=j and a[i]==b[j]:
            i+=1
            j-=1
        if i>j:return True
        return self.isPalindrome(a[i:j+1]) or self.isPalindrome(b[i:j+1])

    def isPalindrome(self, s):
        i = 0
        j = len(s)-1
        while i<=j and s[i]==s[j]:
            i+=1
            j-=1
        return i>j

執行結果

Runtime: 119 ms, faster than 66.67% of Python online submissions for Split Two Strings to Make Palindrome.
Memory Usage: 15.6 MB, less than 38.10% of Python online submissions for Split Two Strings to Make Palindrome.

原題連結:https://leetcode.com/problems/split-two-strings-to-make-palindrome/

您的支援是我最大的動力