# [LeetCode 205. Isomorphic Strings](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/609/week-2-july-8th-july-14th/3811/)
### Daily challenge Jul 12, 2021 (EASY)

>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.

:::info
**Example 1:**
**Input:** s = "egg", t = "add"
**Output:** true
:::

:::info
**Example 2:**
**Input:** s = "foo", t = "bar"
**Output:** false
:::

:::info
**Example 3:**
**Input:** s = "paper", t = "title"
**Output:** true
:::

:::warning
**Constraints:**

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

---

### Approach 1 : Map :bulb:
**`16 ms`**
使用兩個 **unordered_map** 分別紀錄兩個字串的 **`當前元素`** 在此之前 **`最後出現的 index`**。
假設兩者 index 不同， 則表示兩個字串 **not** Isomorphic Strings。

> s = "egg" , t = "add"
> i = 0 ---> map1[e] = map2[a] = 0
> i = 1 ---> map1[g] = map2[d] = 1
> i = 2 ---> g = 1, d = 1 :ok_hand: ---> map1[g] = map2[d] = 2
> **true**

> s = "foo" , t = "bar"
> i = 0 ---> map1[f] = map2[b] = 0
> i = 1 ---> map1[o] = map2[a] = 1
> i = 2 ---> o = 1, r ++*not found*++ ---> **false**

class Solution {
public:
    bool isIsomorphic(string s, string t) {  
        if(s.length() != t.length())    return false;
        
        unordered_map<char, int> index_s;
        unordered_map<char, int> index_t;
        
        for(int i=0; i<s.length(); i++){
            if(index_s.find(s[i]) != index_s.end() || index_t.find(t[i]) != index_t.end()){
                if(index_s.find(s[i]) == index_s.end()
                    || index_t.find(t[i]) == index_t.end()
                    || index_s[s[i]] != index_t[t[i]] )  return false;
            }
            index_s[s[i]] = i;
            index_t[t[i]] = i;
        }
        
        return true;
    }
};

### Approach 2 : Without Maps :book:
**`4 ms`**
與 Approach 1 想法相同。
但改為使用 array[256] 紀錄每個元素出現的位置。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int list1[256];
        int list2[256];
        
        memset(list1, -1, sizeof(list1));
        memset(list2, -1, sizeof(list2));
        
        for(int i=0; i<s.length(); i++){
            if(list1[s[i]] != list2[t[i]])  return false;
            
            list1[s[i]] = i;
            list2[t[i]] = i;
        }
        
        return true;
    }
};