current position:Home>leetcode 1616. Split Two Strings to Make Palindrome (python)
leetcode 1616. Split Two Strings to Make Palindrome (python)
2022-02-01 12:02:26 【Wang Daya】
「 This is my participation 11 The fourth of the yuegengwen challenge 27 God , Check out the activity details :2021 One last more challenge 」
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 code
analysis
According to the meaning , Give two strings of the same length a and b. Select an index and split two strings at the same index , take a Split into two strings :aprefix and asuffix, among a = aprefix + asuffix, take b Split into two strings :bprefix and bsuffix, among b = bprefix + bsuffix. Check aprefix + bsuffix or bprefix + asuffix Whether palindromes are formed .
The string s Split into sprefix and ssuffix when , allow ssuffix or sprefix It's empty . for example , If s = "abc", be "" + "abc"、"a" + "bc"、"ab" + "c" and "abc" + "" Is a valid split . If a palindrome string can be formed, it returns True , Otherwise return to False. Please note that ,x + y Representation string x and y Series connection of .
In fact, it's easy to use greedy thinking in this problem , Join us and we have two strings a and b , And the position divided by the midline assumption , as follows :
- a:AB | CD | EF
- b:GH | KJ | LM
If a And b The suffix of can form palindromes , that AB Definitely and LM Can form palindromes , Then just judge and CD perhaps KJ Whether it is a palindrome , namely :AB+CD+LM perhaps AB+KJ+LM These two situations can form palindromes . take b And a The suffixes of form palindromes are the same logic .
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 code
Running results
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.
Copy code
Original link :leetcode.com/problems/sp…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/02/202202011202244989.html
The sidebar is recommended
- Python from 0 to 1 (day 14) - Python conditional judgment 1
- Several very interesting modules in Python
- How IOS developers learn Python Programming 15 - object oriented programming 1
- Daily python, Chapter 20, exception handling
- Understand the basis of Python collaboration in a few minutes
- [centos7] how to install and use Python under Linux
- leetcode 1130. Minimum Cost Tree From Leaf Values(python)
- leetcode 1433. Check If a String Can Break Another String(python)
- Python Matplotlib drawing 3D graphics
- Talk about deep and shallow copying in Python
guess what you like
-
Python crawler series - network requests
-
Python thread 01 understanding thread
-
Analysis of earthquake distribution in the past 10 years with Python~
-
You need to master these before learning Python crawlers
-
After the old friend (R & D post) was laid off, I wanted to join the snack bar. I collected some data in Python. It's more or less a intention
-
Python uses redis
-
Python crawler - ETF fund acquisition
-
Detailed tutorial on Python operation Tencent object storage (COS)
-
[Python] comparison of list, tuple, array and bidirectional queue methods
-
Go Python 3 usage and pit Prevention Guide
Random recommended
- Python logging log error and exception exception callback method
- Learn Python quickly and take a shortcut~
- Python from 0 to 1 (day 15) - Python conditional judgment 2
- Python crawler actual combat, requests module, python to capture headlines and take beautiful pictures
- The whole activity collected 8 proxy IP sites to pave the way for the python proxy pool, and the 15th of 120 crawlers
- Why can't list be used as dictionary key value in Python
- Python from 0 to 1 (day 16) - Python conditional judgment 3
- What is the python programming language?
- Python crawler reverse webpack, a real estate management platform login password parameter encryption logic
- Python crawler reverse, a college entrance examination volunteer filling platform encrypts the parameter signsafe and decrypts the returned results
- Python simulated Login, selenium module, python identification graphic verification code to realize automatic login
- Python -- datetime (timedelta class)
- Python's five strange skills will bring you a sense of enrichment in mastering efficient programming skills
- [Python] comparison of dictionary dict, defaultdict and orderdict
- Test driven development using Django
- Face recognition practice: face recognition using Python opencv and deep learning
- leetcode 1610. Maximum Number of Visible Points(python)
- Python thread 03 thread synchronization
- Introduction and internal principles of Python's widely used concurrent processing Library Futures
- Python - progress bar artifact tqdm usage
- Python learning notes - the fifth bullet * class & object oriented
- Python learning notes - the fourth bullet IO operation
- Python crawler actual combat: crawl all the pictures in the answer
- Quick reference manual of common regular expressions, necessary for Python text processing
- [Python] the characteristics of dictionaries and collections and the hash table behind them
- Python crawler - fund information storage
- Python crawler actual combat, pyteseract module, python realizes the visualization of boos direct employment & hook post data
- Pit filling summary: Python memory leak troubleshooting tips
- Python code reading (Chapter 61): delaying function calls
- Through the for loop, compare the differences between Python and Ruby Programming ideas
- leetcode 1606. Find Servers That Handled Most Number of Requests(python)
- leetcode 1611. Minimum One Bit Operations to Make Integers Zero(python)
- 06python learning notes - reading external text data
- [Python] functions, higher-order functions, anonymous functions and function attributes
- Python Networkx practice social network visualization
- Data analysis starts from scratch, and pandas reads and writes CSV data
- Python review (format string)
- [pandas learning notes 01] powerful tool set for analyzing structured data
- leetcode 147. Insertion Sort List(python)
- apache2. 4 + windows deployment Django (multi site)