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

打破一个字符串，到底在要求什么

给两个长度相等的字符串 s1 和 s2。说「s1 打破 s2」，指的是能把 s1 重新排列，让它每位都不小于 s2 对应位的字母，这里按字母表算大小，a 最小、z 最大，两位相等也算打破。题目只要求两个方向里成立一个：s1 能打破 s2，或者 s2 能打破 s1，任一为真就返回 true，两个都做不到才返回 false。

逐位比较其实不必枚举排列

想穷举的话，得把 s1 的所有排法都摆出来一个个和 s2 比，长度到 n 就有 n 的阶乘种排法，稍长一点根本算不完。另一个想当然的错是只验一个方向：s1 打不破 s2 就收手报 false，可题目允许反过来让 s2 打破 s1，漏掉这层会把本该 true 的情形判死。

排好序小对小，能打破就一定看得出来

用不着把排法试遍。把两个串各自从小到大排好，再挨位比一次就够。排序给的是最省力的对齐：s1 最小的字母去顶 s2 最小的、次小对次小，每一位的差距都摊得最匀。这靠贪心撑着，贪心就是每步把能定死的顺序先定死、不回头。想更严实可以用交换论证：假设有个更绕的排列能打破，把它调成小对小、大对大，只会更容易满足。排好序这版都打不破，别的排法更没戏。

两串各排一次序，两个方向轮着验

落到步骤上很干脆。先给 s1、s2 各排一次序，再试方向一：看 s1 是不是每位都不小于 s2 的对应位，只要撞见某位 s1 的字母比 s2 小，方向一当场作废。方向一没成也别急着报 false，掉头试方向二：反过来看 s2 是不是每位都不小于 s1。有一个方向全程扛住就是 true，两个都半路断掉才是 false。这里判的是不小于，某位上两个字母相等这位照样算过，若写成严格的 ＞，「aaa」打破「aaa」这种全等情形会被误杀成 false。

「abc」对「xya」，true 怎么逐位走出来

拿题面第一组「abc」对「xya」走一遍。先排序，「abc」本就是升序不动，「xya」理成「axy」。试方向一，要求 s1 每位都不小于 s2：第 0 位 a 对 a，相等算过；第 1 位 b 对 x，b 在字母表里排在 x 前面比它小，方向一断在这。掉头试方向二，要求 s2 每位都不小于 s1：第 0 位 a 对 a 过，第 1 位 x 对 b、x 比 b 大过，第 2 位 y 对 c、y 比 c 大过，三位全扛住。方向二成立，结果 true，和题面一致。

O(n log n) 的账，和三处必判的边界

排序 O(n log n) 是大头：给两个串各排一次是 O(n log n)，之后逐位比是 O(n)，合起来仍是 O(n log n)，n 是字符串长度；额外空间 O(n)，花在排序的字符副本上。收尾时几处最容易栽。只判一个方向就下结论会漏，像「abe」对「acd」，排序后方向一栽在 b 对 c、方向二栽在 d 对 e，两头都断，得都判完才敢返回 false。不排序直接拿原串比也不行，题目要的是存在某个排列，不是原顺序。还有相等这一层，「aaa」对「aaa」每位都相等、按不小于算就是打破，返回 true，这正是不能把条件写成严格大于的原因。

Python

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)
        )

C++

#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;
    }
};

Java

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;
    }
}