【Leetcode】【Easy】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.

Note:
You may assume both s and t have the same length.

解题思路：

如何确定两个字符串是形状相同的，即只依靠替代字母形式，能相互转化；

规律是：字符串s和t中相同位置的字符，所有出现的位置都相同。

如果能记录每个字符出现的位置，同时遍历两个字符串，当遍历到新的字符时，检查各自字符之前出现的位置，之前的位置不一致，则返回false，否则继续检查下一对字符。

对于记录位置和查找操作，最方便的是使用hash字典。字典中记录的是此字符上一次出现的位置。

代码为：

 1 class Solution {
 2 public:
 3     bool isIsomorphic(string s, string t) {
 4         map<char, int> char_s;
 5         map<char, int> char_t;
 6         int len = s.size();
 7         
 8         for (int i = 0; i < len; ++i) {
 9             if (!char_s.count(s[i]))
10                 char_s[s[i]] = i;
11             if (!char_t.count(t[i]))
12                 char_t[t[i]] = i;
13             if (char_s[s[i]] != char_t[t[i]])
14                 return false;
15             char_s[s[i]] = i;
16             char_t[t[i]] = i;
17         }
18         
19         return true;
20     }
21 };