Question

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

English Version

题目描述

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

解法

方法一：排序

将字符串 $s1$, $s2$ 分别进行升序排序。然后同时遍历两个字符串，对应字符进行大小比较。若对于任意 $i∈[0, n)，都有 $s1[i] \le s2[i]$，或者都有 $s1[i] \ge s2[i]$，则存在一个排列可以打破另一个排列。

时间复杂度 $O(nlogn)$。

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

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

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

func checkIfCanBreak(s1 string, s2 string) bool {
  cs1 := []byte(s1)
  cs2 := []byte(s2)
  sort.Slice(cs1, func(i, j int) bool { return cs1[i] < cs1[j] })
  sort.Slice(cs2, func(i, j int) bool { return cs2[i] < cs2[j] })
  check := func(cs1, cs2 []byte) bool {
    for i := range cs1 {
      if cs1[i] < cs2[i] {
        return false
      }
    }
    return true
  }
  return check(cs1, cs2) || check(cs2, cs1)
}

function checkIfCanBreak(s1: string, s2: string): boolean {
  const cs1: string[] = Array.from(s1);
  const cs2: string[] = Array.from(s2);
  cs1.sort();
  cs2.sort();
  const check = (cs1: string[], cs2: string[]) => {
    for (let i = 0; i < cs1.length; i++) {
      if (cs1[i] < cs2[i]) {
        return false;
      }
    }
    return true;
  };
  return check(cs1, cs2) || check(cs2, cs1);
}