Friday, July 31, 2015

Leetcode 205: isomorphic strings

Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

isomorphic string 其实考察的是找一一映射的关系,最直接的方法就是用两个map来记录两个string 的各个字符对应的位置,而同一位置上的字符在Map对应的位置应该相同。
由于map对象是string,所以用256个int的 array更加节省空间,可以直接用256个int array来代替map,其实对于string,更加节省空间的方式是bit map, 每一个bit对应一个字符,但是bit map的缺点是只能取值0 , 1.所以只能判断duplicate情况,对于更加复杂一些的情况是不好进行处理的。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        //sanity check
        if (s.size() == 0 && t.size() == 0 ) return true;
        if (s.size() != t.size()) return false;
        int M1[256] = {0};
        int M2[256] = {0};
        for (int i = 0; i < s.size();i++) {
            if (M1[s[i]] != M2[t[i]]) return false;
            M1[s[i]] = i+1;
            M2[t[i]] = i+1;
        }
        return true;
    }
};

No comments:

Post a Comment