思路讲解与算法实现 LeetCode - 判定是否互为字符重排

每天一道公司算法真题，讲解解题思路与各种算法实现；欢迎大家点评或者说出你的解题想法，或评论想让我讲解哪道题！

题目

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

示例1：

• 输入： s1 = “abc”, s2 = “bca”
• 输出：true

示例2：

• 输入：s1 = “abc”, s2 = “bad”
• 输出：false

说明

• 0 <= len(s1) <= 100
• 0 <= len(s2) <= 100

解法一

只要2个字符串中的每一个字符的个数都能对应上，就能重拍。也就是要统计每一个字符的个数，因为题目没有说字符有哪些，即不一定全部是字母。所以我们借助map数据结构来存放统计数据，因为2个字符串的相同字符个数要相等，所以它们的个数相减就必须等于0。

package com.nobody;

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

/**
 * @Description 给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
 * @Author Mr.nobody
 * @Date 2021/4/18
 * @Version 1.0
 */
public class CheckPermutation {
   

    public boolean checkPermutation(String s1, String s2) {
   
        // 长度不相等，肯定不能重排
        if (s1.length() != s2.length()) {
   
            return false;
        }
        // 存放s1和s2中相同字符个数相减后的个数
        Map<Character, Integer> nums = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
   
            // 记录s1每一个字符的个数
            nums.put(s1.charAt(i), nums.getOrDefault(s1.charAt(i), 0) + 1);
            // 减去s2每一个字符的个数
            nums.put(s2.charAt(i), nums.getOrDefault(s2.charAt(i), 0) - 1);
        }
        // 如果相减后全部字符的个数都为0，则代表可以重排
        return nums.values().stream().allMatch(num -> num == 0);
    }

    public static void main(String[] args) {
   
        CheckPermutation cp = new CheckPermutation();
        String s1 = "abcd", s2 = "cbdd";
        System.out.println(cp.checkPermutation(s1, s2));
    }
}

解法二

可以将字符串转换为字符数组，然后进行排序，如果排序后的字符串仍然相同，则它们是可以重排的。

package com.nobody;

import java.util.Arrays;

/**
 * @Description 给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。abc和bac是，abc和dca不是。
 * @Author Mr.nobody
 * @Date 2021/4/18
 * @Version 1.0
 */
public class CheckPermutation {
   

    public boolean checkPermutation(String s1, String s2) {
   
        // 长度不相等，肯定不能重排
        if (s1.length() != s2.length()) {
   
            return false;
        }
        // 排序
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        // 对比排序后的字符串
        return new String(chars1).equals(new String(chars2));
    }

    public static void main(String[] args) {
   
        CheckPermutation cp = new CheckPermutation();
        String s1 = "abcd", s2 = "cbda";
        System.out.println(cp.checkPermutation(s1, s2));
    }
}

上下篇

上一篇：思路讲解与算法实现 LeetCode - 判定字符是否唯一

下一篇：敬请期待

转载：https://blog.csdn.net/chenlixiao007/article/details/115826907