題目
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.
Note:
You may assume both s and t have the same length.
解題之法
class Solution {
public:
bool isIsomorphic(string s, string t) {
int m1[256] = {0}, m2[256] = {0}, n = s.size();
for (int i = 0; i < n; ++i) {
if (m1[s[i]] != m2[t[i]]) return false;
m1[s[i]] = i + 1;
m2[t[i]] = i + 1;
}
return true;
}
};
分析
這道題讓我們求同構字符串，就是說原字符串中的每個字符可由另外一個字符替代，可以被其本身替代效览，相同的字符一定要被同一個字符替代，且一個字符不能被多個字符替代椒振，即不能出現(xiàn)一對多的映射拿穴。根據(jù)一對一映射的特點，我們需要用兩個哈希表分別來記錄原字符串和目標字符串中字符出現(xiàn)情況席舍，由于ASCII碼只有256個字符梢什，所以我們可以用一個256大小的數(shù)組來代替哈希表奠蹬，并初始化為0，我們遍歷原字符串嗡午，分別從源字符串和目標字符串取出一個字符囤躁，然后分別在兩個哈希表中查找其值，若不相等荔睹，則返回false割以，若想等，將其值更新為i + 1应媚。
