LeetCode 题解工作台
检查一个字符串是否可以打破另一个字符串
给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1 的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1 的一个排列。 字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i （在 0 到 n - 1 之间）都有 x[i] >= y…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
将字符串 , 分别进行升序排序。然后同时遍历两个字符串，对应字符进行大小比较。若对于任意 $i∈[0, n)，都有 $s1[i] \le s2[i]$，或者都有 $s1[i] \ge s2[i]$，则存在一个排列可以打破另一个排列。 时间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你两个字符串 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 == ns2.length == n1 <= n <= 10^5- 所有字符串都只包含小写英文字母。
解题思路
方法一：排序
将字符串 , 分别进行升序排序。然后同时遍历两个字符串，对应字符进行大小比较。若对于任意 s1[i] \le s2[i]s1[i] \ge s2[i]$，则存在一个排列可以打破另一个排列。
时间复杂度 。
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)
)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate effectively applies sorting and greedy techniques.
- question_mark
The candidate recognizes the greedy choice property and validates it appropriately.
- question_mark
The candidate can explain the invariant used for string comparison after sorting.
常见陷阱
外企场景- error
Overlooking the need to sort the strings before comparison.
- error
Failing to handle edge cases, such as strings with different characters or lengths.
- error
Assuming a brute force approach to check all permutations without recognizing the efficiency of sorting.
进阶变体
外企场景- arrow_right_alt
Check if one string can break another with case-sensitive comparison.
- arrow_right_alt
Extend the problem to check if two strings of different lengths can break each other with additional constraints.
- arrow_right_alt
Implement a solution using dynamic programming to verify the breaking condition without sorting.