程序员面试金典：面试题 01.02. 判定是否互为字符重排

• 题目
• 简化
• 思路
• 伪代码
• • 直接使用Map
  • 使用数组模拟哈希表
• Java代码
• • 直接使用Map
  • 使用数组模拟哈希表

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

示例 1：

输入: s1 = “abc”, s2 = “bca”
输出: true
示例 2：

输入: s1 = “abc”, s2 = “bad”
输出: false
说明：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-permutation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

输入：

• str1, str2。
• str1和str2是否互为重排序，str1和str2可能字母重复。
• 0 <= len(s1, s2) <= 100
• 隐藏条件，题目没有说明，字母全部为小写字母

长度不一样返回false
存储每个字母和其出现的次数，因为字符串总长是100，所以选择byte类型即可。

伪代码

function CheckPermutation(String s1, String s2) {
	if (s1.len != s2.len) {
		return false;
	}
	
	Map map = new Map()

	for (c : s1) {
		count = set.getOrDefault(c, 0)
		
		map.put(c, count)
	}
	
	for (c : s2) {
		count = map.get(c)
		count = count - 1
	}

	for (v : map.values()) {
		if (v != 0) {
			return false
		}
	}

	return true
}

其实因为只有26个字母，所以可以使用数组模拟哈希表。

伪代码

function CheckPermutation(String s1, String s2) {
	if (s1.len != s2.len) {
		return false;
	}

	// 小写字母，所以26个空间足够了
	byte[] bytes = new byte[26];
	
	for (char c : s1) {
		bytes[c - 'a']++;
	}

	for (char c : s2) {
		// 有字符在s2中出现，却在s1中没有出现过，直接返回false
		if (bytes[c - 'a'] == 0) {
			return false;
		}
		
		bytes[c - 'a']--;
	}

	for (byte b : bytes) {
		if (b != 0) {
			return false;
		}
	}
	
	return true;
}

public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }

        Map map = new HashMap<>();

        char[] chars1 = s1.toCharArray();

        for (char c : chars1) {
            byte count = map.getOrDefault(c, (byte)0);
            map.put(c, (byte)(count + 1));
        }

        char[] chars2 = s2.toCharArray();

        for (char c : chars2) {
            Byte count;
            if ((count = map.get(c)) != null) {
                map.put(c, (byte)(count - 1));
            } else {
                return false;
            }
        }

        for (Byte b : map.values()) {
            if (b != 0) {
                return false;
            }
        }

        return true;
    }

public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }

        byte[] bytes = new byte[26];

        char[] chars1 = s1.toCharArray();

        for (char c : chars1) {
            bytes[c - 'a']++;        
        }

        char[] chars2 = s2.toCharArray();

        for (char c : chars2) {
            if (bytes[c - 'a'] == 0) {
            	return false;
            }
            
            bytes[c - 'a']--;
        }

        for (byte b : bytes) {
            if (b != 0) {
                return false;
            }
        }

        return true;
    }