快捷導(dǎo)航

Java C++題解leetcode判定是否為字符重排

更新時(shí)間：2022年09月29日 15:01:51 作者：AnjaVon

這篇文章主要為大家介紹了Java C++題解leetcode判定是否為字符重排，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

思路一：排序

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

時(shí)間復(fù)雜度：O(n log n)，排序復(fù)雜度
空間復(fù)雜度：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;
    }
};

時(shí)間復(fù)雜度：O(nlog?n)O(n\log n)O(nlogn)，排序復(fù)雜度
空間復(fù)雜度：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
        }
    }
}

時(shí)間復(fù)雜度：O(n log? n)，排序復(fù)雜度
空間復(fù)雜度：O(n)，拷貝字符串用于排序

思路二：詞頻統(tǒng)計(jì)

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

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(C)，常數(shù)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;
    }
};

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(C)，常數(shù)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)
    }
}