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

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

Example 3:

Input: s1 = "leetcodee", s2 = "interview"
Output: true
Copy the code

Note:

s1.length == n
s2.length == n
1 <= n <= 10^5
All strings consist of lowercase English letters.
Copy the code

parsing

Given two strings s1 and s2 of the same length, check whether some permutations of string S1 can break some permutations of string S2, and vice versa. In short, S2 can destroy S1 and vice versa. If x[I] >= y[I] (in alphabetical order) for all I between 0 and n-1, it means that string x can break string y (both of length n).

In this case, we need to sort s1 and S2 in ascending order, and then compare whether the characters in s1 are larger or smaller than s2.

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

The results

Runtime: 176 ms, faster than 86.67% of Python online submissions for checking If a String Can Break Another String. Memory Usage: The linked list in the Python online submissions for Check If a String Can Break Another String.Copy the code

parsing

The principle is similar to the above, except to determine whether the number of characters larger or smaller than s2 is equal to the length of S1.

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

The results

Runtime: 238 ms, faster than 53.33% of Python online submissions for Check If a String Can Break Another String. Memory Usage: Given in the Python online submissions for Check If a String Can Break Another String.Copy the code

Original link: leetcode.com/problems/ch…

Your support is my biggest motivation