current position:Home>leetcode 1433. Check If a String Can Break Another String(python)
leetcode 1433. Check If a String Can Break Another String(python)
2022-02-01 02:00:16 【Wang Daya】
「 This is my participation 11 The fourth of the yuegengwen challenge 21 God , Check out the activity details :2021 One last more challenge 」
describe
Given two strings: s1 and s2 with the same size, check if some permutation of string s1 can break some permutation of string s2 or vice-versa. In other words s2 can break s1 or vice-versa.
A string x can break string y (both of size n) if x[i] >= y[i] (in alphabetical order) for all i between 0 and n-1.
Example 1:
Input: s1 = "abc", s2 = "xya"
Output: true
Explanation: "ayx" is a permutation of s2="xya" which can break to string "abc" which is a permutation of s1="abc".
Copy code
Example 2:
Input: s1 = "abe", s2 = "acd"
Output: false
Explanation: All permutations for s1="abe" are: "abe", "aeb", "bae", "bea", "eab" and "eba" and all permutation for s2="acd" are: "acd", "adc", "cad", "cda", "dac" and "dca". However, there is not any permutation from s1 which can break some permutation from s2 and vice-versa.
Copy code
Example 3:
Input: s1 = "leetcodee", s2 = "interview"
Output: true
Copy code
Note:
s1.length == n
s2.length == n
1 <= n <= 10^5
All strings consist of lowercase English letters.
Copy code
analysis
According to the meaning , Given two strings of the same length s1 and s2, Check string s1 Whether some permutations of can break the string s2 Some permutations of , vice versa . In short, it is ,s2 Can destroy s1, vice versa . If for 0 and n-1 Between all i ,x[i] >= y[i]( In alphabetical order ), Represents a string x You can break the string y( The length is n ).
In fact, after reading the title, we will know that it is actually judgment s1 Than s2 The characters in the corresponding position are large or small , This situation must be right s1 and s2 Sort in ascending order , Then compare whether you are satisfied s1 Than s2 The characters in the corresponding position are large or small .
answer
class Solution(object):
def checkIfCanBreak(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
s1 = list(s1)
s2 = list(s2)
s1.sort()
s2.sort()
def check(s1, s2):
for i in range(len(s1)):
if s1[i] < s2[i]:
return False
return True
return check(s1, s2) or check(s2, s1)
Copy code
Running results
Runtime: 172 ms, faster than 86.67% of Python online submissions for Check If a String Can Break Another String.
Memory Usage: 19.9 MB, less than 53.33% of Python online submissions for Check If a String Can Break Another String.
Copy code
analysis
Similar to the principle above , It's just judgment s1 Than s2 Whether the number of characters with large or small corresponding positions is equal to s1 The length of .
answer
class Solution(object):
def checkIfCanBreak(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
s1 = sorted(s1)
s2 = sorted(s2)
a = b = 0
n = len(s1)
for i in range(len(s1)):
if s1[i] <= s2[i]:
a += 1
if s1[i] >= s2[i]:
b += 1
return a == n or b == n
Copy code
Running results
Runtime: 228 ms, faster than 53.33% of Python online submissions for Check If a String Can Break Another String.
Memory Usage: 20.2 MB, less than 26.67% of Python online submissions for Check If a String Can Break Another String.
Copy code
Original link :leetcode.com/problems/ch…
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/202202010200143873.html
The sidebar is recommended
- Python avatar animation, come and generate your own animation avatar
- leetcode 1884. Egg Drop With 2 Eggs and N Floors(python)
- leetcode 1910. Remove All Occurrences of a Substring(python)
- Python and binary
- First acquaintance with Python class
- [Python data collection] scrapy book acquisition and coding analysis
- Python crawler from introduction to mastery (IV) extracting information from web pages
- Python crawler from entry to mastery (III) implementation of simple crawler
- The apscheduler module in Python implements scheduled tasks
- 1379. Find the same node in the cloned binary tree (Java / C + + / Python)
guess what you like
-
Python connects redis, singleton and thread pool, and resolves problems encountered
-
Python from 0 to 1 (day 11) - Python data application 1
-
Python bisect module
-
Python + OpenGL realizes real-time interactive writing on blocks with B-spline curves
-
Use the properties of Python VTK implicit functions to select and cut data
-
Learn these 10000 passages and become a humorous person in the IT workplace. Python crawler lessons 8-9
-
leetcode 986. Interval List Intersections(python)
-
leetcode 1860. Incremental Memory Leak(python)
-
How to teach yourself Python? How long will it take?
-
Python Matplotlib drawing pie chart
Random recommended
- Django paging (II)
- Concurrent. For Python concurrent programming Futures or multiprocessing?
- Programmers over the age of 25 can't know a few Chinese herbal medicines. Python crawler lessons 9-9
- Python crawler from introduction to pit full series of tutorials (detailed tutorial + various practical combat)
- The second bullet of class in Python
- Python object oriented programming 03: class inheritance and its derived terms
- How IOS developers learn Python Programming 13 - function 4
- Python crawler from introduction to mastery (VI) form and crawler login
- Python crawler from entry to mastery (V) challenges of dynamic web pages
- Deeply understand pandas to read excel, TXT, CSV files and other commands
- Daily python, Chapter 18, class
- "I just want to collect some plain photos in Python for machine learning," he said. "I believe you a ghost!"
- Django view
- Python implements filtering emoticons in text
- When winter comes, python chooses a coat with temperament for mom! Otherwise, there's really no way to start!
- Python crawler - get fund change information
- Highlight actor using Python VTK
- Python crawler actual combat: crawling southern weekend news articles
- leetcode 406. Queue Reconstruction by Height(python)
- leetcode 1043. Partition Array for Maximum Sum (python)
- Python * * packaging and unpacking details
- Python realizes weather query function
- Python from 0 to 1 (day 12) - Python data application 2 (STR function)
- Python from 0 to 1 (day 13) - Python data application 3
- Numpy common operations of Python data analysis series Chapter 8
- How to implement mockserver [Python version]
- Van * Python! Write an article and publish the script on multiple platforms
- Python data analysis - file reading
- Python data De duplication and missing value processing
- Python office automation - play with browser
- Python series tutorial 127 -- Reference vs copy
- Control flow in Python: break and continue
- Teach you how to extract tables in PDF with Python
- leetcode 889. Construct Binary Tree from Preorder and Postorder Traversal(python)
- leetcode 1338. Reduce Array Size to The Half(python)
- Object oriented and exception handling in Python
- How to configure load balancing for Django service
- How to embed Python in go
- Python Matplotlib drawing graphics
- Python object-oriented programming 05: concluding summary of classes and objects