Medium

题目描述

给定两个长度相同的字符串 s1 和 s2，检查 s1 的某个排列是否可以打破 s2 的某个排列，反之亦然。换句话说，s1 可以打破 s2 或者 s2 可以打破 s1。

如果字符串 x 可以打破字符串 y（两者长度都为 n），那么对于所有 0 到 n-1 之间的 i，都有 x[i] >= y[i]（按字母顺序）。

示例 1：

输入：s1 = "abc", s2 = "xya"
输出：true
解释："ayx" 是 s2="xya" 的一个排列，它可以打破字符串 "abc"，而 "abc" 是 s1="abc" 的一个排列。

示例 2：

输入：s1 = "abe", s2 = "acd"
输出：false
解释：s1="abe" 的所有排列都是："abe", "aeb", "bae", "bea", "eab" 和 "eba"，s2="acd" 的所有排列都是："acd", "adc", "cad", "cda", "dac" 和 "dca"。然而，不存在 s1 的任何排列可以打破 s2 的某个排列，反之亦然。

示例 3：

输入：s1 = "leetcodee", s2 = "interview"
输出：true

提示：

  • s1.length == n
  • s2.length == n
  • 1 <= n <= 10^5
  • 所有字符串都由小写英文字母组成

解题思路

解题思路

这道题要求判断一个字符串的某个排列是否可以"打破"另一个字符串的某个排列。关键在于理解"打破"的定义：对于相同位置的字符，前者必须在字母表中大于等于后者。

核心观察：要使一个字符串的排列能够打破另一个字符串的排列，最优策略是：

  • 将第一个字符串按降序排列（尽可能把大字符放在前面）
  • 将第二个字符串按升序排列（尽可能把小字符放在前面）

这样能最大化第一个字符串"打破"第二个字符串的可能性。

算法步骤：

  1. 对两个字符串分别进行排序
  2. 检查 s1 排序后（降序）是否可以打破 s2 排序后（升序）
  3. 检查 s2 排序后（降序）是否可以打破 s1 排序后（升序）
  4. 只要有一种情况成立就返回 true

时间复杂度主要来自排序操作，为 O(n log n)。由于我们需要对字符串进行排序，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    bool checkIfCanBreak(string s1, string s2) {
        // 对两个字符串分别排序
        string sorted_s1 = s1, sorted_s2 = s2;
        sort(sorted_s1.begin(), sorted_s1.end());
        sort(sorted_s2.begin(), sorted_s2.end());
        
        // 检查s1降序是否可以打破s2升序
        bool s1_breaks_s2 = true;
        for (int i = 0; i < s1.length(); i++) {
            if (sorted_s1[s1.length() - 1 - i] < sorted_s2[i]) {
                s1_breaks_s2 = false;
                break;
            }
        }
        
        // 检查s2降序是否可以打破s1升序
        bool s2_breaks_s1 = true;
        for (int i = 0; i < s2.length(); i++) {
            if (sorted_s2[s2.length() - 1 - i] < sorted_s1[i]) {
                s2_breaks_s1 = false;
                break;
            }
        }
        
        return s1_breaks_s2 || s2_breaks_s1;
    }
};

class Solution:
    def checkIfCanBreak(self, s1: str, s2: str) -> bool:
        # 对两个字符串分别排序
        sorted_s1 = sorted(s1)
        sorted_s2 = sorted(s2)
        
        # 检查s1降序是否可以打破s2升序
        s1_breaks_s2 = all(c1 >= c2 for c1, c2 in zip(sorted(s1, reverse=True), sorted_s2))
        
        # 检查s2降序是否可以打破s1升序
        s2_breaks_s1 = all(c2 >= c1 for c2, c1 in zip(sorted(s2, reverse=True), sorted_s1))
        
        return s1_breaks_s2 or s2_breaks_s1

public class Solution {
    public bool CheckIfCanBreak(string s1, string s2) {
        // 对两个字符串分别排序
        char[] arr1 = s1.ToCharArray();
        char[] arr2 = s2.ToCharArray();
        Array.Sort(arr1);
        Array.Sort(arr2);
        
        // 检查s1降序是否可以打破s2升序
        bool s1BreaksS2 = true;
        for (int i = 0; i < s1.Length; i++) {
            if (arr1[s1.Length - 1 - i] < arr2[i]) {
                s1BreaksS2 = false;
                break;
            }
        }
        
        // 检查s2降序是否可以打破s1升序
        bool s2BreaksS1 = true;
        for (int i = 0; i < s2.Length; i++) {
            if (arr2[s2.Length - 1 - i] < arr1[i]) {
                s2BreaksS1 = false;
                break;
            }
        }
        
        return s1BreaksS2 || s2BreaksS1;
    }
}

var checkIfCanBreak = function(s1, s2) {
    // 对两个字符串分别排序
    const sorted_s1 = s1.split('').sort();
    const sorted_s2 = s2.split('').sort();
    
    // 检查s1降序是否可以打破s2升序
    let s1_breaks_s2 = true;
    for (let i = 0; i < s1.length; i++) {
        if (sorted_s1[s1.length - 1 - i] < sorted_s2[i]) {
            s1_breaks_s2 = false;
            break;
        }
    }
    
    // 检查s2降序是否可以打破s1升序
    let s2_breaks_s1 = true;
    for (let i = 0; i < s2.length; i++) {
        if (sorted_s2[s2.length - 1 - i] < sorted_s1[i]) {
            s2_breaks_s1 = false;
            break;
        }
    }
    
    return s1_breaks_s2 || s2_breaks_s1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(n)

说明：

  • 时间复杂度：主要来自对两个字符串的排序操作，每次排序需要 O(n log n) 时间
  • 空间复杂度：需要额外空间存储排序后的字符数组，为 O(n)