Java C++题解leetcode判定是否为字符重排

题目要求

思路一:排序

Java

class Solution {
 public boolean CheckPermutation(String s1, String s2) {
 if(s1.length() != s2.length())
 return false;
 char[] sort1 = s1.toCharArray();
 Arrays.sort(sort1);
 char[] sort2 = s2.toCharArray();
 Arrays.sort(sort2);
 return Arrays.equals(sort1, sort2);
 }
}
  • 时间复杂度:O(n log n),排序复杂度
  • 空间复杂度:O(n),拷贝字符串用于排序

C++

class Solution {
public:
 bool CheckPermutation(string s1, string s2) {
 if (s1.size() != s2.size())
 return false;
 sort(s1.begin(), s1.end());
 sort(s2.begin(), s2.end());
 return s1 == s2;
 }
};
  • 时间复杂度:O(nlog⁡n)O(n\log n)O(nlogn),排序复杂度
  • 空间复杂度:O(log⁡n)O(\log n)O(logn),排序需要

Rust

impl Solution {
 pub fn check_permutation(s1: String, s2: String) -> bool {
 if s1.len() != s2.len() {
 false
 }
 else {
 let (mut sort1, mut sort2) = (s1.as_bytes().to_vec(), s2.as_bytes().to_vec());
 sort1.sort();
 sort2.sort();
 sort1 == sort2
 }
 }
}
  • 时间复杂度:O(n log⁡ n),排序复杂度
  • 空间复杂度:O(n),拷贝字符串用于排序

思路二:词频统计

Java

class Solution {
 public boolean CheckPermutation(String s1, String s2) {
 if(s1.length() != s2.length())
 return false;
 int[] freq = new int[128];
 int diff = 0;
 for (int i = 0; i < s1.length(); i++) {
 if (++freq[s1.charAt(i)] == 1)
 diff++;
 if (--freq[s2.charAt(i)] == 0)
 diff--;
 }
 return diff == 0;
 }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(C),常数C为字符集大小

C++

class Solution {
public:
 bool CheckPermutation(string s1, string s2) {
 if (s1.size() != s2.size())
 return false;
 int freq[128];
 memset(freq, 0, sizeof(freq));
 int diff = 0;
 for (int i = 0; i < s1.size(); i++) {
 if (++freq[s1[i]] == 1)
 diff++;
 if (--freq[s2[i]] == 0)
 diff--;
 }
 return diff == 0;
 }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(C),常数C为字符集大小

Rust

impl Solution {
 pub fn check_permutation(s1: String, s2: String) -> bool {
 s1.len() == s2.len() && s1.bytes().zip(s2.bytes()).fold(vec![0; 128], |mut freq, (c1, c2)| {
 freq[c1 as usize] += 1;
 freq[c2 as usize] -= 1;
 freq
 }).into_iter().all(|diff| diff == 0)
 }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(C),常数C为字符集大小

总结

简单模拟题、快乐结束~

有些语言不能改的字符串在这种时候真是烦烦……

作者:AnjaVon

%s 个评论

要回复文章请先登录注册