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

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

题目要求

思路一：排序

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