程序员面试金典【2 】-- 判断是否互为字符串重排

秦怀杂货店

发布于 2022-02-15 15:03:38

3210

文章被收录于专栏：技术杂货店技术杂货店

💻 剑指Offer & LeetCode刷题仓库：https://github.com/Damaer/CodeSolution
- 文档地址：https://damaer.github.io/CodeSolution/
- 仓库介绍：刷题仓库：CodeSolution
📒 编程知识库：https://github.com/Damaer/Coding
- 文档地址：https://damaer.github.io/Coding/#/

1题目

给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。（全部是小写字母）

示例 1：

输入: s1 = "abc", s2 = "bca" 输出: true

示例 2：

输入: s1 = "abc", s2 = "bad" 输出: false

2思路以及解答

这是一道比较简单的题目，但是我们可以多想想一些解法：

1. 先排序再比较

既然需要对比是不是重排后的字符串，那么我们把两个字符串都按照相同的规则排序，排序完之后再挨个对比，就可以判断两个字符串是不是互为重排字符串了。

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1 == null && s2 == null) {
            return true;
        }
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
            return false;
        }
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        for (int i = 0; i < chars1.length; i++) {
            if (chars1[i] != chars2[i]) {
                return false;
            }
        }
        return true;
    }
}

上面的方式不仅使用了额外的空间，还用了排序算法，空间复杂度为 O(n), 时间复杂度为 O(nlogn + n)，排序算法为 O(nlogn)，但是遍历的时间复杂度为 O(n)。

2. 统计数值

其实，我们不需要排序，如果重排，我们只需要统计每个字符出现的次数即可，两个字符串出现的字符数量是不一致的话，那么肯定不是重排的。

下面我们使用 HashMap 来统计每一个字符出现的次数：

import java.util.HashMap;
import java.util.Map;

public class Solution2 {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1 == null && s2 == null) {
            return true;
        }
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
            return false;
        }
        Map<Character, Integer> count1 = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            if (count1.get(s1.charAt(i)) != null) {
                count1.put(s1.charAt(i), count1.get(s1.charAt(i)) + 1);
            } else {
                count1.put(s1.charAt(i), 1);
            }
        }
        Map<Character, Integer> count2 = new HashMap<>();
        for (int i = 0; i < s2.length(); i++) {
            if (count2.get(s2.charAt(i)) != null) {
                count2.put(s2.charAt(i), count1.get(s2.charAt(i)) + 1);
            } else {
                count2.put(s2.charAt(i), 1);
            }
        }

        for (Map.Entry<Character, Integer> entry : count1.entrySet()) {
            if (count2.get(entry.getKey()) != entry.getValue()) {
                return false;
            }
        }
        return true;
    }
}

没有了排序，时间复杂度下降了，时间复杂度和空间复杂度都是 O(n)。

3. 数组优化空间，提前返回结果

上面用的是 HashMap，其实我们可以用更加轻量级的数据结构，比如数组，我们知道，字符的种类是有限的，特别是这道题限制了全部都是小写字母，那么我们直接用大小为 26 的数组即可，这样压缩了空间。

前面我们是都统计完两个字符串之后，才进行对比，其实我们可以在统计第一个字符串的时候用加法，在统计第二个字符串的时候用减法，当出现负数的时候，那么就肯定不是重排字符串。

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1 == null && s2 == null) {
            return true;
        }
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
            return false;
        }
        int[] counts = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            counts[s1.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s2.length(); i++) {
            if (counts[s2.charAt(i) - 'a'] == 0) {
                return false;
            }
            counts[s2.charAt(i) - 'a']--;
        }
        return true;
    }
}

空间复杂度其实是常数级，时间复杂度仍旧为 O(n)，只是减少了不必要的循环。

【作者简介】

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，Redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-12-10，如有侵权请联系 cloudcommunity@tencent.com 删除

https