题目描述

给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例 1：

1
2
输入: s1 = "abc", s2 = "bca"
输出: true

示例 2：

1
2
输入: s1 = "abc", s2 = "bad"
输出: false

说明：

  • 0 <= len(s1) <= 100
  • 0 <= len(s2) <= 100

来源：力扣（LeetCode）

题解

排序

1
2
3
4
5
6
7
8
public boolean CheckPermutation(String s1, String s2) {
    if (s1.length() != s2.length()) return false;
    char[] charArr1 = s1.toCharArray();
    char[] charArr2 = s2.toCharArray();
    Arrays.sort(charArr1);
    Arrays.sort(charArr2);
    return Arrays.equals(charArr1, charArr2);
}
  • 时间复杂度： O(nlogn)
  • 空间复杂度： O(logn)*，排序需要 *O(logn) 的空间复杂度。注意，在某些语言（比如 Java & JavaScript）中字符串是不可变的，因此我们需要额外的 O(n) 的空间来拷贝字符串。但是我们忽略这一复杂度分析，因为：
    • 这依赖于语言的细节；
    • 这取决于函数的设计方式，例如，可以将函数参数类型更改为 char[]。

submissions-2022092701

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean CheckPermutation(String s1, String s2) {
    // 如果字符串长度不一致, 那么无论如何排序两个字符串都不可能相等
    if (s1.length() != s2.length()) return false;
    int[] countArr = new int[256];
    for (char c : s1.toCharArray()) countArr[c]++;
    for (char c : s2.toCharArray()) {
        countArr[c]--;
        // 这里只需要判断 count[c] 是否小于 0 即可.
        // 如果有 count[c] > 0, 由于两个字符串长度一致, 所以必定存在 count[c] < 0, 那么一定会返回 false
        if (countArr[c] < 0) return false;
    }
    return true;
}
  • 时间复杂度： O(n)
  • 空间复杂度： O(S)*，其中 *S 为字符集大小，此处为 S = 256。

submissions-2022092702

参考资料

__END__