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.
- You may assume both s and t have the same length.
Example:
- Given "egg", "add", return true.
- Given "foo", "bar", return false.
- Given "paper", "title", return true.
C Solution:
bool isIsomorphic(char* s, char* t) {
int flag[256] = {0}, _flag[245] = {0};
int i;
for (i = 0; s[i]; i++) {
if (flag[s[i]] != _flag[t[i]]) return false;
flag[s[i]] = _flag[t[i]] = i + 1;
}
return true;
}
Python Solution 1:
class Solution(object):
def isIsomorphic(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if len(s) != len(t): return False
ds = {}
dt = {}
for i in range(len(s)):
if s[i] not in ds and t[i] not in dt:
ds[s[i]] = t[i]
dt[t[i]] = s[i]
continue
if s[i] in ds and t[i] in dt and ds[s[i]] == t[i] and dt[t[i]] == s[i]: continue
return False
return True
Python Solution 2:
class Solution(object):
def isIsomorphic(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if len(s) != len(t): return False
ds = {}
dt = {}
for i in range(len(s)):
if s[i] not in ds and t[i] not in dt:
ds[s[i]] = i
dt[t[i]] = i
continue
if s[i] in ds and t[i] in dt and ds[s[i]] == dt[t[i]]: continue
return False
return True
Summary:
- The solution is beautiful.
LeetCode: 205. Isomorphic Strings
近期评论