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

记牢一句:两个串各自排好序,逐位比;s1 全程 ≥ s2,或者 s2 全程 ≥ s1,任一成立就能打破。下面每帧都在套这句。

原始 · 两个串：上排是 s1 = 「dbace」,右边侧栏是 s2 = 「fcbed」,两个串长度都是 5。直接看原始顺序没法逐位比,所以第一步,把它们各自从小到大排好序。

第一步 · s1 排序：先排 s1。把 「dbace」 从小到大理一遍,得到 「abcde」,现在上排就是排好的样子。接着排 s2。

第一步 · s2 排序：s2 也排一遍,「fcbed」 理顺成 「bcdef」,放进右边侧栏。现在上排 s1 是 「abcde」,侧栏 s2 是 「bcdef」,位置一一对齐,可以逐位比了。

就位 · 两个方向二选一：两行都排好了。接下来要试两个方向:方向一,看 s1 是不是每一位都 ≥ s2;方向二,看 s2 是不是每一位都 ≥ s1。任意一个方向全程成立,就能打破。先试方向一。

方向一 · s1 能打破 s2 吗：方向一的要求很明确:排好序后,s1 的每一位都要 ≥ s2 的对应位。只要有一位 s1 比 s2 小,方向一当场就不成立。从第 0 位开始。

方向一 · 第 0 位：第 0 位,上排 s1 是 「a」,侧栏 s2 是 「b」。方向一要的是 s1 ≥ s2,也就是 「a」 要不小于 「b」。比一下。

方向一 · 断在第 0 位：「a」 在字母表里排在 「b」 前面,也就是 「a」 < 「b」。s1 的第 0 位反而比 s2 小,方向一的「每位都 ≥」当场被打破,这一格标红。方向一不成立。

方向一不行 → 试方向二：方向一断了,可别急着说答案是 false。题目是「两个方向有一个成立就行」,s1 打不破 s2,还要反过来看 s2 能不能打破 s1。清空颜色,试方向二。

方向二 · s2 能打破 s1 吗：方向二的要求对称过来:排好序后,s2 的每一位都要 ≥ s1 的对应位。同样从第 0 位开始,一位一位往后比,中途有一位栽了就算方向二也失败。

方向二 · 第 0 位：看第 0 位。侧栏 s2 是 「b」,上排 s1 是 「a」。方向二要 s2 ≥ s1,也就是 「b」 要不小于 「a」。

方向二 · 第 0 位通过：「b」 在字母表里不比 「a」 靠前,也就是 「b」 ≥ 「a」,这一位满足方向二的要求,标绿。已经连过 1 位,接着看下一位。

方向二 · 第 1 位：看第 1 位。侧栏 s2 是 「c」,上排 s1 是 「b」。方向二要 s2 ≥ s1,也就是 「c」 要不小于 「b」。

方向二 · 第 1 位通过：「c」 在字母表里不比 「b」 靠前,也就是 「c」 ≥ 「b」,这一位满足方向二的要求,标绿。已经连过 2 位,接着看下一位。

方向二 · 第 2 位：看第 2 位。侧栏 s2 是 「d」,上排 s1 是 「c」。方向二要 s2 ≥ s1,也就是 「d」 要不小于 「c」。

方向二 · 第 2 位通过：「d」 在字母表里不比 「c」 靠前,也就是 「d」 ≥ 「c」,这一位满足方向二的要求,标绿。已经连过 3 位,接着看下一位。

方向二 · 第 3 位：看第 3 位。侧栏 s2 是 「e」,上排 s1 是 「d」。方向二要 s2 ≥ s1,也就是 「e」 要不小于 「d」。

方向二 · 第 3 位通过：「e」 在字母表里不比 「d」 靠前,也就是 「e」 ≥ 「d」,这一位满足方向二的要求,标绿。已经连过 4 位,接着看下一位。

方向二 · 第 4 位：看第 4 位。侧栏 s2 是 「f」,上排 s1 是 「e」。方向二要 s2 ≥ s1,也就是 「f」 要不小于 「e」。

方向二 · 第 4 位通过：「f」 在字母表里不比 「e」 靠前,也就是 「f」 ≥ 「e」,这一位满足方向二的要求,标绿。已经连过 5 位。

方向二 · 成立：五位全部走完,s2 的每一位都 ≥ s1 的对应位,一格都没栽。方向二成立,s2 可以打破 s1,上排整排标绿。

完成 · 答案 true：回看全程:方向一在第 0 位就断了,但方向二每一位都成立。题目只要两个方向有一个能打破就行,所以答案是 true,跟开头说的对上了。这就是排序后逐位比、两个方向二选一的全过程。

边界:abc 对 xya 靠方向二成立;abe 对 acd 两个方向都断为 false;全 a 对全 a 因为相等也算打破,返回 true。

面试重点:排序后逐位比是贪心最优配对(交换论证);两个方向不对称、都要试;字符集 26 时可用计数排序把整体压到 O(n)。