Isomorphic Strings using C++
Asked 1 year ago
0Comments
1 Views
Imagine we're playing a secret code game with words!
Let's say we have two words: "EGG" and "ADD"
We want to know if we can turn "EGG" into "ADD" by replacing letters, but we have to follow some special rules:
- Each letter in "EGG" must change to the same letter in "ADD" every time it appears.
- Two different letters in "EGG" can't change into the same letter in "ADD".
- We can't change the order of the letters.
E -> A
G -> D
EGG -> ADD
Let's try it:
P -> T
A -> I
P -> T (already done)
E -> L
R -> E
PAPER -> TITLEBut what about "FOO" and "BAR"?
F -> B
O -> A
O -> ?Uh oh! We have a problem. We already used 'A' for the second letter, so we can't use it again for the third letter. There's no way to make this work, so......
"FOO" and "BAR" are not isomorphic.
The trick is to make sure that:
- Each letter always changes to the same new letter.
- We never use the same new letter for two different original letters
class Solution {
public:
bool isIsomorphic(string s, string t) {
int hash[256] = {0} ;
bool isSecondCharsMapped[256] = {0};
// stores if t[i] is mapped wiht s[i]
// also checks if mapping already happend or not
for(int i =0 ; i< s.size() ; i++){
if(hash[s[i]]==0 && isSecondCharsMapped[t[i]] == 0 ){
// then Map
hash[s[i]] = t[i] ;
isSecondCharsMapped[t[i]] = true ;
}
}
for(int i= 0 ; i<s.size() ; i++){
if(hash[s[i]] != t[i]){
return false ;
}
}
return true ;
}
};The clever part of your solution is:
- Using the
hashbox to remember what each letter should change into. - Using the
isSecondCharsMappedbox to make sure we don't use the same disguise twice. - Checking twice: once to set up the code, and once to make sure it works for the whole word.
Feel free to checkout one more problem with similar approch !
Share