题目描述

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

示例 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__