“This is the 27th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”

describe

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
Copy the code

parsing

Given two strings a and B of the same length. Select an index and split two strings at the same index, split A into two strings: aprefix and asuffix, where a = aprefix + asuffix, split B into two strings: Bprefix and bsuffix, where b = bprefix + bsuffix. Check whether aprefix + bsuffix or bPrefix + asuffix form a palindrome.

When splitting the string s into sprefix and ssuffix, ssuffix or sprefix is allowed to be empty. For example, if the s = “ABC”, “” +” ABC “, “a” + “BC”, “ab” + “c” and “ABC”, “” is an effective resolution. Return True if a palindrome string can be formed, False otherwise. Note that x + y represents the concatenation of the strings x and y.

Let’s add that we have two strings a and B, and use the center line to assume the location of the partition, as follows:

  • A: AB | | EF CD
  • B: GH | KJ | LM

If the prefix of A and the suffix of B can form a palindrome, then AB and LM must form a palindrome, then only need to judge and CD or KJ is palindrome, namely: AB+CD+LM or AB+KJ+LM these two cases can form a palindrome. The same logic applies to the palindrome of the prefix b and the suffix A.

answer

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
        

        	      
		
Copy the code

The results

Runtime: 136 ms, faster than 66.67% of Python online submissions for Split Two Strings to Make Palindrome. Memory Usage: The linked submissions in the Python online submissions list for Split Two Strings to Make Palindrome.Copy the code

Original link: leetcode.com/problems/sp…

Your support is my biggest motivation