leetcode 1616. Split Two Strings to Make Palindrome （python）_王大呀呀

「這是我參與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: a_prefix and a_suffix where a = a_prefix + a_suffix, and splitting b into two strings: b_prefix and b_suffix where b = b_prefix + b_suffix. Check if a_prefix + b_suffix or b_prefix + a_suffix forms a palindrome.

When you split a string s into s_prefix and s_suffix, either s_suffix or s_prefix 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:
a_prefix = "", a_suffix = "x"
b_prefix = "", b_suffix = "y"
Then, a_prefix + b_suffix = "" + "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:
a_prefix = "ula", a_suffix = "cfd"
b_prefix = "jiz", b_suffix = "alu"
Then, a_prefix + b_suffix = "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 拆分為兩個字串：a_prefix 和 a_suffix，其中 a = a_prefix + a_suffix，將 b 拆分為兩個字串：b_prefix 和 b_suffix，其中 b = b_prefix + b_suffix。檢查 a_prefix + b_suffix 或 b_prefix + a_suffix 是否形成迴文。

將字串 s 拆分為 s_prefix 和 s_suffix 時，允許 s_suffix 或 s_prefix 為空。例如，如果 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/

您的支援是我最大的動力