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

标签: 贪心 字符串 排序

难度: Medium

给你两个字符串 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
  • 所有字符串都只包含小写英文字母。

Submission

运行时间: 75 ms

内存: 16.6 MB

class Solution:
    def checkIfCanBreak(self, s1: str, s2: str) -> bool:
        c1 = Counter(s1)
        c2 = Counter(s2)

        chars = [chr(ord('a') + i) for i in range(26)]

        acc1 = accumulate(c1[ch] for ch in chars)
        acc2 = accumulate(c2[ch] for ch in chars)

        acc1, acc2 = list(acc1), list(acc2)

        return all(a1 <= a2 for a1, a2 in zip(acc1, acc2)) or \
               all(a1 >= a2 for a1, a2 in zip(acc1, acc2))

Explain

为了解决问题，我们采用了基于计数的方法。首先，我们分别统计两个字符串s1和s2中每个字符出现的次数。接着，我们创建一个字符列表chars，包含了所有小写字母。然后，我们使用累积函数accumulate，基于chars中的字符顺序来计算s1和s2中每个字符以及之前所有字符的累积出现次数。这样得到的两个累积列表acc1和acc2，可以用来比较两个字符串的字典序。最后，我们检查s1的任意排列是否可以打破s2的任意排列，或者s2的任意排列是否可以打破s1的任意排列。具体地，如果acc1中的每个位置的值都小于等于acc2对应位置的值，或者acc1中的每个位置的值都大于等于acc2对应位置的值，返回true。否则返回false。

时间复杂度: O(n)

空间复杂度: O(1)

from collections import Counter
from itertools import accumulate

class Solution:
    def checkIfCanBreak(self, s1: str, s2: str) -> bool:
        # 创建字母的计数
        c1 = Counter(s1)
        c2 = Counter(s2)
        
        # 生成所有小写字母的列表
        chars = [chr(ord('a') + i) for i in range(26)]
        
        # 计算字符累积分布
        acc1 = list(accumulate(c1[ch] for ch in chars))
        acc2 = list(accumulate(c2[ch] for ch in chars))
        
        # 检查s1的累积分布是否总是小于等于s2的，或者总是大于等于s2的
        return all(a1 <= a2 for a1, a2 in zip(acc1, acc2)) or \
               all(a1 >= a2 for a1, a2 in zip(acc1, acc2))

Explore

使用字符计数和累积分布的方法可以提供更高效的解决方案。直接排序两个字符串的时间复杂度是O(n log n)，其中n是字符串的长度。而通过统计字符出现的频次并使用累积分布，我们仅需O(n)时间来统计频次加上O(1)时间来比较每个字符的累积分布（因为字符集大小是常数，即26个小写英文字母）。这样，总的时间复杂度降至O(n)，从而更高效地处理大数据量的情况。

是的，这种情况已经考虑在内。在计算累积分布时，如果某个字符在字符串中不存在，`Counter`对象会返回0。因此，对于不存在的字符，累积分布中该字符的值会与前一个字符的累积值相同。这保证了累积分布的连续性，即使某些字符在字符串中完全缺失也不会影响最终的比较结果。

在构建累积分布列表`acc1`和`acc2`时，我们基于固定的字符列表`chars`，它包含了所有26个小写字母。因此，无论输入字符串`s1`和`s2`中的字符如何，`acc1`和`acc2`都是基于相同的26个字母进行累积计数的，保证了两个列表的长度始终为26，从而确保了比较过程中列表长度的一致性。

在`checkIfCanBreak`函数中，通过两个`all`条件来分别检查是否存在一种情况，即`s1`的每个字符的累积出现次数始终小于等于`s2`的对应累积次数，或者`s1`的累积次数始终大于等于`s2`的累积次数。如果其中一个条件为真，表示至少有一种排列方式使得一个字符串可以完全打破另一个字符串（即，一个字符串的每个字符在字典序上不小于另一个字符串的相应位置的字符，或者总是不大于）。这是因为累积分布考虑了字符的整体分布趋势，而不仅仅是单个位置上的比较。