检查一个字符串是否可以打破另一个字符串 图解题解

这道题到底在问什么

输入

s1="abc", s2="xya"

输出

true

输入

s1="abe", s2="acd"

输出

false

输入

s1="leetcodee", s2="interview"

输出

true

最优解：一步一步想明白

1. 3记牢一句:两个串各自排好序,逐位比;s1 全程 ≥ s2,或者 s2 全程 ≥ s1,任一成立就能打破。下面每帧都在套这句。
2. 4上排是 s1 = 「dbace」,右边侧栏是 s2 = 「fcbed」,两个串长度都是 5。直接看原始顺序没法逐位比,所以第一步,把它们各自从小到大排好序。
3. 5先排 s1。把 「dbace」 从小到大理一遍,得到 「abcde」,现在上排就是排好的样子。接着排 s2。
4. 6s2 也排一遍,「fcbed」 理顺成 「bcdef」,放进右边侧栏。现在上排 s1 是 「abcde」,侧栏 s2 是 「bcdef」,位置一一对齐,可以逐位比了。
5. 7两行都排好了。接下来要试两个方向:方向一,看 s1 是不是每一位都 ≥ s2;方向二,看 s2 是不是每一位都 ≥ s1。任意一个方向全程成立,就能打破。先试方向一。
6. 8方向一的要求很明确:排好序后,s1 的每一位都要 ≥ s2 的对应位。只要有一位 s1 比 s2 小,方向一当场就不成立。从第 0 位开始。
7. 9第 0 位,上排 s1 是 「a」,侧栏 s2 是 「b」。方向一要的是 s1 ≥ s2,也就是 「a」 要不小于 「b」。比一下。
8. 10「a」 在字母表里排在 「b」 前面,也就是 「a」 < 「b」。s1 的第 0 位反而比 s2 小,方向一的「每位都 ≥」当场被打破,这一格标红。方向一不成立。
9. 11方向一断了,可别急着说答案是 false。题目是「两个方向有一个成立就行」,s1 打不破 s2,还要反过来看 s2 能不能打破 s1。清空颜色,试方向二。
10. 12方向二的要求对称过来:排好序后,s2 的每一位都要 ≥ s1 的对应位。同样从第 0 位开始,一位一位往后比,中途有一位栽了就算方向二也失败。
11. 13看第 0 位。侧栏 s2 是 「b」,上排 s1 是 「a」。方向二要 s2 ≥ s1,也就是 「b」 要不小于 「a」。
12. 14「b」 在字母表里不比 「a」 靠前,也就是 「b」 ≥ 「a」,这一位满足方向二的要求,标绿。已经连过 1 位,接着看下一位。
13. 15看第 1 位。侧栏 s2 是 「c」,上排 s1 是 「b」。方向二要 s2 ≥ s1,也就是 「c」 要不小于 「b」。
14. 16「c」 在字母表里不比 「b」 靠前,也就是 「c」 ≥ 「b」,这一位满足方向二的要求,标绿。已经连过 2 位,接着看下一位。
15. 17看第 2 位。侧栏 s2 是 「d」,上排 s1 是 「c」。方向二要 s2 ≥ s1,也就是 「d」 要不小于 「c」。
16. 18「d」 在字母表里不比 「c」 靠前,也就是 「d」 ≥ 「c」,这一位满足方向二的要求,标绿。已经连过 3 位,接着看下一位。
17. 19看第 3 位。侧栏 s2 是 「e」,上排 s1 是 「d」。方向二要 s2 ≥ s1,也就是 「e」 要不小于 「d」。
18. 20「e」 在字母表里不比 「d」 靠前,也就是 「e」 ≥ 「d」,这一位满足方向二的要求,标绿。已经连过 4 位,接着看下一位。
19. 21看第 4 位。侧栏 s2 是 「f」,上排 s1 是 「e」。方向二要 s2 ≥ s1,也就是 「f」 要不小于 「e」。
20. 22「f」 在字母表里不比 「e」 靠前,也就是 「f」 ≥ 「e」,这一位满足方向二的要求,标绿。已经连过 5 位。
21. 23五位全部走完,s2 的每一位都 ≥ s1 的对应位,一格都没栽。方向二成立,s2 可以打破 s1,上排整排标绿。
22. 24回看全程:方向一在第 0 位就断了,但方向二每一位都成立。题目只要两个方向有一个能打破就行,所以答案是 true,跟开头说的对上了。这就是排序后逐位比、两个方向二选一的全过程。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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)
        )

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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;
    }
};

import java.util.*;
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;
    }
}

复杂度

面试官可能追问