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