https://leetcode.com/problems/isomorphic-strings/description/
Solution 0. Store the same index for the last appearance of s[i] and t[i] to two arrays. If the indices for s[i] and t[i] are different, they are not isomorphic.
bool isIsomorphic(string s, string t) {
if(s.size() != t.size()) return false;
int mps[256] = {0}, mpt[256] = {0};
for(int i=0; i<s.size(); i++) {
if(mps[s[i]] != mpt[t[i]])
return false;
mps[s[i]] = i+1;
mpt[t[i]] = i+1;
}
return true;
}
Solution 1. Use array as map
bool isIsomorphic(string s, string t) {
if(s.size() != t.size()) return false;
//vector<char> mps(256, 0), mpt(256, 0);
char mps[256] = {0};
char mpt[256] = {0};
for(int i=0; i<s.size(); i++) {
if(!mps[s[i]] && !mpt[t[i]]) {
mps[s[i]] = t[i];
mpt[t[i]] = s[i];
}
else if(mps[s[i]] != t[i] || mpt[t[i]] != s[i])
return false;
}
return true;
}
Solution 1.1 use map
bool isIsomorphic(string s, string t) {
if(s.size() != t.size()) return false;
unordered_map<char,char> mp, mq;
for(int i=0; i<s.size(); i++) {
if(!mp.count(s[i]) && !mq.count(t[i])) {
mp[s[i]] = t[i];
mq[t[i]] = s[i];
}
else if(mp[s[i]] != t[i] || mq[t[i]] != s[i]) return false;
}
return true;
}
No comments:
Post a Comment