Leetcode Study Day 19

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings s and t 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.

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
 

Constraints:

1 <= s.length <= 5 * 104
t.length == s.length
s and t consist of any valid ascii character.

My solution

My solution is using unordered_map to store the mapping between characters in s and t. We loop through the string s and check if the character is in the unordered_map. If it is, we check if the character in t is the same as the character in unordered_map. If it is not, we return false. If it is, we continue to check the next character in s. After the iteration, we can make sure that all the characters in s can be mapped to t.

Then we clear the unordered_map and do the same thing for t and s. If all the characters in t can be mapped to s, we return true. Otherwise, we return false.

An example if we only check s and t once:

s = "badc"
t = "baba"

In this case, if we only check whether the characters in s can be mapped to t, we will get the result true. However, the character b in the string t can be mapped to a and d in the string s. Therefore, we need to check whether the characters in t can be mapped to s as well.

Full code

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) return false;
        unordered_map<char, char> wordMatch;
        for (int i = 0; i < s.size(); i ++){
            auto ifMatch = wordMatch.find(s[i]);
            // don't find the element in the map
            if (ifMatch == wordMatch.end())
                wordMatch[s[i]] = t[i];
            // find the element in the map
            if (ifMatch != wordMatch.end()){
                if (wordMatch[s[i]] != t[i])
                    return false;
            }
        }
        wordMatch.clear();
        for (int i = 0; i < t.size(); i ++){
            auto ifMatch = wordMatch.find(t[i]);
            // don't find the element in the map
            if (ifMatch == wordMatch.end())
                wordMatch[t[i]] = s[i];
            // find the element in the map
            if (ifMatch != wordMatch.end()){
                if (wordMatch[t[i]] != s[i])
                    return false;
            }
        }        
        return true;
    }
};