JavaC++题解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为字符集大小

总结

简单模拟题、快乐结束~

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

以上就是Java C++题解leetcode判定是否为字符重排的详细内容，更多关于Java C++ 判定是否为字符重排的资料请关注编程宝库其它相关文章！

Windows内核中是无法使用vector容器等数据结构的，当我们需要保存一个结构体数组时，就需要使用内核中提供的专用链表结构LIST_ENTRY通过一些列链表操作函数对结构体进行装入弹出等操作，如下代码是本 ...