題目概述：

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.

解題方法：
? ? ? ? 該題意是判斷兩個字符串s和t是否是同構的。（注意字符不僅是字母）
? ? ? ? 最簡單的方法是通過計算每個字符出現的個數并且相應位置字母對應，但是兩層循環肯定TLE。所以需要通過O(n)時間比較，采用的方法是：
? ? ? ? eg： "aba" <> "baa" ?return false
? ? ? ? 關鍵代碼：nums[s[i]]=t[i] ?numt[t[i]]=s[i] 再比較是否相同?
? ? ? ? nums['a']='b' numt['b']='a' ?(第一次出現)
? ? ? ? nums['b']='a' numt['a']='b' ?(第一次出現)
? ? ? ? nums['a']='b' <> t[2]='a' ? ? (第二次出現) ?return false
? ? ? ? 該方法技巧性比較強，當然如果你使用C++的映射就非常容易實現了。

我的代碼：

bool isIsomorphic(char* s, char* t) {int ls,lt; //字符串長度int i,j;int nums[256]={0};int numt[256]={0};ls = strlen(s);lt = strlen(t);if(ls!=lt) return false;for(i=0; i<ls; i++) {//初值為0if(nums[s[i]]==0) {if(numt[t[i]]==0) {nums[s[i]] = t[i];numt[t[i]] = s[i];}else {return false;}}else {if(nums[s[i]]!=t[i]) {return false;}}}return true; }

C++推薦代碼：

? ? ? ? 參考：http://www.cnblogs.com/easonliu/p/4465650.html
? ? ? ? 題目很簡單，也很容易想到方法，就是記錄遍歷s的每一個字母，并且記錄s[i]到t[i]的映射，當發現與已有的映射不同時，說明無法同構，直接return false。但是這樣只能保證從s到t的映射，不能保證從t到s的映射，所以交換s與t的位置再重來一遍上述的遍歷就OK了。

class Solution { public:bool isIsomorphic(string s, string t) {if (s.length() != t.length()) return false;map<char, char> mp;for (int i = 0; i < s.length(); ++i) {if (mp.find(s[i]) == mp.end()) mp[s[i]] = t[i];else if (mp[s[i]] != t[i]) return false;}mp.clear();for (int i = 0; i < s.length(); ++i) {if (mp.find(t[i]) == mp.end()) mp[t[i]] = s[i];else if (mp[t[i]] != s[i]) return false;}return true;} };

(By:Eastmount 2015-9-21 凌晨1點半???http://blog.csdn.net/eastmount/)

總結

以上是生活随笔為你收集整理的[LeetCode] Isomorphic Strings - 字符串操作:数组计数字符个数问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。