Java/C++/Rust 判定字符重排：排序与词频统计解法

题目要求

给定两个字符串 s1 和 s2，判断它们是否由完全相同的字符组成，只是排列顺序不同。如果相同则返回 true，否则返回 false。

思路一：排序法

第1步：长度校验

无论采用何种策略，首先需检查两个字符串的长度。若长度不一致，直接判定为不构成重排，提前返回 false。这是所有解法的通用前置条件。

第2步：字符排序与比对

若将两个字符串中的字符分别进行排序，排序后的结果应当完全一致。该方法逻辑直观，易于实现，但排序操作本身会带来额外的时间开销。

Java 实现

Java 中可通过 toCharArray() 获取字符数组并利用 Arrays.sort() 进行排序，最后使用 Arrays.equals() 比较结果。

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++ 实现

C++ 利用 STL 的 std::sort 对 string 对象直接排序，随后通过重载的 == 运算符进行比较。需注意 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(n log n)
• 空间复杂度：O(log n)，快排递归栈深度

Rust 实现

Rust 中字符串切片不可变且需处理字节级操作。通常先将字符串转换为可变字节向量 Vec，调用 sort() 后再进行逐字节比较。注意区分 char（Unicode标量值）与 u8（字节），本题假设仅涉及 ASCII 或按字节重排时可用字节比较。

impl Solution {
    pub fn check_permutation(s1: String, s2: String) -> bool {
        if s1.len() != s2.len() {
            return false;
        }
        let mut sort1 = s1.as_bytes().to_vec();
        let mut sort2 = s2.as_bytes().to_vec();
        sort1.sort();
        sort2.sort();
        sort1 == sort2
    }
}

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)，拷贝字节数据用于排序

思路二：词频统计法

为了优化性能，可以使用定长数组记录每个字符出现的次数差。遍历两个字符串，在 s1 中累加计数，在 s2 中减去计数。最终若所有位置均为 0，说明两者字符频率一致。

第1步：初始化计数器

创建一个大小为 128 的整型数组（覆盖标准 ASCII 码），初始化为 0。同时维护一个 diff 变量，记录当前非零计数的种类数量或净差值变化。

第2步：同步遍历更新

并行遍历 s1 和 s2 的对应位置索引 i。对于 s1[i]，对应频次 +1；对于 s2[i]，对应频次 -1。通过观察频次变化的临界点更新 diff 值，避免最后再次全量扫描数组。

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; // 记录当前有几种字符频次不为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=128 为常数级空间

C++ 实现

C++ 可使用 memset 快速清零数组，逻辑同 Java。

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)，固定大小数组

Rust 实现

Rust 可以通过函数式风格结合迭代器实现紧凑的逻辑，但在实际工程中对性能和可读性的平衡需仔细考量。此处展示一种基于 fold 的写法：

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(|val| val == 0)
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(C)，生成并清理临时向量

总结

判定字符重排是考察基础数据结构操作的经典题目。排序法代码极简，适合理解概念，但在大数据量下性能受限；词频统计法虽然代码稍多，但将时间复杂度降低至线性级别，且由于 ASCII 字符集限制，空间占用极小，是更优的工程实践选择。在实际开发中，面对不可变字符串的语言（如 Rust 默认 String 或 Java String），需特别注意内存拷贝的成本。

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