[LeetCode]205. Isomorphic Strings

Problem

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.

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:

Input: s = "egg", t = "add"
Output: true
Example 2:

Input: s = "foo", t = "bar"
Output: false
Example 3:

Input: s = "paper", t = "title"
Output: true

Note:

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

Solution

Analysis

题目给定两个串,判断两者是不是同一种格式.比如例一:”egg”和”add”, 两者都可以表示为”ABB”格式; 例二”foo”和”bar”,格式分别为”ABB”和”ABC”,例三”paper”和”title”分别为”ABACD”和”ABACD”.

所以,我可以写一个辅助函数归纳一个字符串的格式, 这里的格式不仅和字符出现的频率有关,而且和字符之间的顺序相关, 因为题目中给定都是小写字母,本来想归纳到数字上,但是由于数字之间不具有区分关系,’123’不能分辨出来,到底是”1”和”23”还是”12”和”3”还是”1”和”2”和”3”. 所以统一归纳到大写字母上.

还有一种相对简单的关系,不用统一映射到”ABC”上, 两个串之间直接相互映射: s->t, t->s. 然后逐个记录映射关系,比较映射关系,得到最终答案.

Code

Solution One

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
bool isIsomorphic(string s, string t) {
if (s == t) return true;

if (convert(s) == convert(t))
return true;
return false;
}
private:
// 统一到ABCD上, 找到当前字符串的表达公式, eg:abb -> ABB, cdd->ABB
// 两个原串进行转换,判断各自的表达公式是否相同.
string convert(string s){
unordered_map<char, char> tabel;// 方便归纳"ABA"等, 这种出现重复字符的情况.
char start = 'A';
string result = "";
for (auto ch : s){
if (tabel.find(ch) != tabel.end()){// found
result += tabel[ch];
}else{// not exists
result += start;
tabel[ch] = start;
++start;
}
}

return result;
}
};

Solution Two

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
bool isIsomorphic(string s, string t) {
char sTotMap[256] = {0};
char tTosMap[256] = {0};

int i = 0, j = 0;

while (i < s.size() && j < t.size()){
// s To t mapping
if (sTotMap[s[i]] != 0){// 重复出现
if (sTotMap[s[i]] != t[j])//判断映射是否正确
return false;
}else// 没出现,记录映射关系
sTotMap[s[i]] = t[j];

// t To s mapping
if (tTosMap[t[j]] != 0){//和上面类似
if (tTosMap[t[j]] != s[i])
return false;
}else
tTosMap[t[j]] = s[i];

++i;
++j;
}
return true;
}
};

References

您的支持就是我更新的最大动力!谢谢!