leetcode 1433. Check If a String Can Break Another String（python）

語言: CN / TW / HK
時間 2021-11-21 10:15:07

「這是我參與11月更文挑戰的第21天，活動詳情檢視：2021最後一次更文挑戰」

描述

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".

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.

Example 3:

Input: s1 = "leetcodee", s2 = "interview"
Output: true

Note:

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

解析

根據題意，給定長度相同的兩個字串 s1 和 s2，檢查字串 s1 的某些排列是否可以破壞字串 s2 的某些排列，反之亦然。 簡單說就是，s2 可以破壞 s1，反之亦然。如果對於 0 和 n-1 之間的所有 i ，x[i] >= y[i]（按字母順序），則表示字串 x 可以斷開字串 y（長度均為 n ）。

其實看完題目我們就知道其實就是判斷 s1 比 s2 對應位置上的字元都大或者都小，這種情況就要都對 s1 和 s2 進行升序排序，然後比較是不是滿足 s1 比 s2 對應位置上的字元都大或者都小。

解答

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)

執行結果

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.

解析

和上面的原理類似，只不過是判斷 s1 比 s2 對應位置字元都大或者都小的個數是否等於 s1 的長度。

解答

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

執行結果

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.

原題連結：http://leetcode.com/problems/check-if-a-string-can-break-another-string/

您的支援是我最大的動力

「」
「」