题目描述

给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1  的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1 的一个排列。

字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序）。

样例

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

输入：s1 = "abe", s2 = "acd"
输出：false 
解释：
s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba" ，
s2="acd" 的所有排列包括："acd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。
然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。

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

提示：

• s1.length == n
• s2.length == n
• 1 <= n <= 10^5
• 所有字符串都只包含小写英文字母。

算法分析

贪心 + 排序

• 1、对于两个字符串的某一排列，只需要其中一个字符串的所有元素满足x[i] >= y[i]即可，即数组x[]中最小的字符和数组y[]最小的字符比较，第二小的字符和第二小的字符比较,…最大的字符和最大的字符比较
• 2、对两个字符串内的元素从小到大排序，若存在对任意的x[i] >= y[i]，或x[i] <= y[i]，则表示可以打破，否则不可以打破

时间复杂度 $O(nlogn)$

Java 代码

class Solution {
    public boolean checkIfCanBreak(String s1, String s2) {
        int n = s1.length();
        char[] g1 = s1.toCharArray();
        char[] g2 = s2.toCharArray();
        Arrays.sort(g1);
        Arrays.sort(g2);

        boolean flag = true;
        for(int i = 0;i < n;i ++)
        {
            if(g1[i] < g2[i]) flag = false;
        }
        if(flag) return true;
        flag = true;

        for(int i = 0;i < n;i ++)
        {
            if(g1[i] > g2[i]) flag = false;
        }
        if(flag) return true;

        return false;
    }
}