跳转至

1433. 检查一个字符串是否可以打破另一个字符串

题目描述

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

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

 

示例 1：

输入：s1 = "abc", s2 = "xya"
输出：true
解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，且 "ayx" 可以打破 "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 的排列。也没有 s2 的排列能打破 s1 的排列。

示例 3：

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

 

提示：

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

解法

方法一：排序

将字符串 $s1$, $s2$ 分别进行升序排序。然后同时遍历两个字符串，对应字符进行大小比较。若对于任意 $i∈[0, n)，都有 $s1[i] \le s2[i]$，或者都有 $s1[i] \ge s2[i]$，则存在一个排列可以打破另一个排列。

时间复杂度 $O(nlogn)$。

1
2
3
4
5
6
7
class Solution:
    def checkIfCanBreak(self, s1: str, s2: str) -> bool:
        cs1 = sorted(s1)
        cs2 = sorted(s2)
        return all(a >= b for a, b in zip(cs1, cs2)) or all(
            a <= b for a, b in zip(cs1, cs2)
        )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean checkIfCanBreak(String s1, String s2) {
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        Arrays.sort(cs1);
        Arrays.sort(cs2);
        return check(cs1, cs2) || check(cs2, cs1);
    }

    private boolean check(char[] cs1, char[] cs2) {
        for (int i = 0; i < cs1.length; ++i) {
            if (cs1[i] < cs2[i]) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool checkIfCanBreak(string s1, string s2) {
        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());
        return check(s1, s2) || check(s2, s1);
    }

    bool check(string& s1, string& s2) {
        for (int i = 0; i < s1.size(); ++i) {
            if (s1[i] < s2[i]) {
                return false;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func checkIfCanBreak(s1 string, s2 string) bool {
    cs1 := []byte(s1)
    cs2 := []byte(s2)
    sort.Slice(cs1, func(i, j int) bool { return cs1[i] < cs1[j] })
    sort.Slice(cs2, func(i, j int) bool { return cs2[i] < cs2[j] })
    check := func(cs1, cs2 []byte) bool {
        for i := range cs1 {
            if cs1[i] < cs2[i] {
                return false
            }
        }
        return true
    }
    return check(cs1, cs2) || check(cs2, cs1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function checkIfCanBreak(s1: string, s2: string): boolean {
    const cs1: string[] = Array.from(s1);
    const cs2: string[] = Array.from(s2);
    cs1.sort();
    cs2.sort();
    const check = (cs1: string[], cs2: string[]) => {
        for (let i = 0; i < cs1.length; i++) {
            if (cs1[i] < cs2[i]) {
                return false;
            }
        }
        return true;
    };
    return check(cs1, cs2) || check(cs2, cs1);
}

评论