单射，满射，双射

• 单射：集合2中的一个元素不能被集合1中的多个元素所映射
• 满射：集合2中的每一个元素都能在集合1中找到原象
• 双射：一个映射，既是单射，也是满射

例题1.同构字符串

• 链接：LeetCode205.同构字符串

思路

设两个集合分别为A，B
由于哈希表存储的是单向关系，所以证明双射需要用两个哈希表
证明单射：B中的一个元素不能被A中的多个元素所映射，需要开一个从B->A的哈希表
证明满射：由于两个集合元素个数必须相同，所以一定是满射
证明这是一个映射关系：A中的元素不能对应多个B中的元素，需要开一个A->B的哈希表

这类题和集合论中的双射有一点不一样：就是元素必须是有保序的

Java代码

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character,Character> st = new HashMap<>();
        Map<Character,Character> ts = new HashMap<>();
        for(int i = 0; i < s.length(); i++){
            char a = s.charAt(i), b = t.charAt(i);
            if(st.containsKey(a) && st.get(a) != b) return false;
            st.put(a,b);
            if(ts.containsKey(b) && ts.get(b) != a) return false;
            ts.put(b,a);
        }
        return true;
    }
}

例题2.单词规律

• 链接：LeetCode290.单词规律

思路

这题和上一题完全一样

Java代码

class Solution {
    public boolean wordPattern(String pattern, String str) {
        String[] words = str.split(" ");
        //不是满射
        if(words.length != pattern.length()) return false;
        Map<Character,String> pw = new HashMap<>();
        Map<String,Character> wp = new HashMap<>();
        char[] p = pattern.toCharArray();
        for(int i = 0; i < p.length; i++){
            char a = p[i];
            String b = words[i];
            //判断f是否为映射：一个a不能对应多个b
            if(pw.containsKey(a) && !pw.get(a).equals(b)) return false;
            pw.put(a,b);
            //判断f是否为单射：一个b不能被多个a对应
            if(wp.containsKey(b) && wp.get(b) != a) return false;
            wp.put(b,a);
        }
        return true;
    }
}