`

Leetcode - Isomorphic Strings

 
阅读更多
[分析]
思路1:维护两个哈希表,char[] map, boolean[] used, 长度均为256,map[charS] = charT, 表示将字符charS 映射为charT, used[charT]==true 表示charT已经被某个字符映射过了。同步遍历字符串s & t,记两者当前的字符分别为charS, charT, 若charS是新字符,且charT没有被使用,则我们可将其同charT建立映射关系,否则说明有两个不同的字符试图映射到同一个字符上,不符合要求;若charS已被建立映射关系,则检查charT是否和charS的映射字符相等,不相等不符合题目要求的“All occurrences of a character must be replaced with another character ”。
思路2:参考https://leetcode.com/discuss/33854/my-6-lines-solution,又是一个怎巧妙了得~ 这个思路也是用两个哈希表,不同于思路1直接将s中的字符映射到t中字符,它是将s 和 t中的字符同时映射到下标上,因为若个字符若存在映射关系,则必然是出现在相同的下标位置,实现中由于初始值为0,建立映射时使用 i + 1,以区分未映射状态和映射到下标为0的状态。

public class Solution {
    // Method 2 https://leetcode.com/discuss/33854/my-6-lines-solution
    public boolean isIsomorphic(String s, String t) {
        int[] map1 = new int[256];
        int[] map2 = new int[256];
        for (int i = 0; i < s.length(); i++) {
            if (map1[s.charAt(i)] != map2[t.charAt(i)])
                return false;
            map1[s.charAt(i)] = i + 1;
            map2[t.charAt(i)] = i + 1;
        }
        return true;
    }
    // Method 1
    public boolean isIsomorphic1(String s, String t) {
        if (s == null || t == null) return false;
        char[] map = new char[256];
        boolean[] used = new boolean[256];
        for (int i = 0; i < s.length(); i++) {
            char charS = s.charAt(i);
            char charT = t.charAt(i);
            if (map[charS] == 0) {
                if (used[charT]) return false; // No two characters may map to the same character 
                map[charS] = charT;
                used[charT] = true;
            } else if (map[charS] != charT){
                return false; // All occurrences of a character must be replaced with another character 
            }
        }
        return true;
    }
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics