leetcode筆記：Isomorphic Strings

一.題目描述

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.

For example,
Given “egg”, “add”, return true.

Given “foo”, “bar”, return false.

Given “paper”, “title”, return true.

Note:
You may assume both s and t have the same length.

二.題目分析

這道題主要是建立兩個字符串中不同字符的對應關系，由於ASCII編碼的字符只有256個，而且string中是不保存null字符的，因此，可以建立兩個大小為256的字符數組來保存兩個string中每一個字符在另外一個string中的對應的關系，然後遍歷string中的每一個字符，如果相同位置的字符是互相對應的話，就處理下一個字符，如果不是互相對應的話，就在說明這兩個string不是同等結構的。

也可以通過兩個map來實現，但是map的查找過程時間復雜度為O(lgn)，但是上面對於string中的每一個字符串都需要查找，因此，使用map的話，時間復雜度太高了。也可以使用hash表來做，也就是使用unordered_map來實現，但是由於ASCII編碼的字符的個數是固定的而且個數比較少，使用數組完全可以很好地實現。

三.示例代碼

#include   
#include   

using std::string;  
using std::vector;  

class Solution  
{  
public:  
    bool isIsomorphic(string s, string t)  
    {  
        vector First(256, 0); // 創建一個含有256個0拷貝的vector
        vector Second(256, 0);  

        const int SIZE = s.size();  

        for (int Index = 0; Index < SIZE; Index++)  
        {  
            unsigned char ElementOfFirst = s[Index];  
            unsigned char ElementOfSecond = t[Index];  

            unsigned char& First2Second = First[ElementOfSecond];  
            unsigned char& Second2First = Second[ElementOfFirst];  

            if (First2Second != 0 && Second2First != 0)  
            {  

                if (First2Second != ElementOfFirst)  
                {  
                    return false;  
                }  


                if (Second2First != ElementOfSecond)  
                {  
                    return false;  
                }  
                continue;  
            }  

            if (First2Second == 0 && Second2First == 0)  
            {  
                First2Second = ElementOfFirst;  
                Second2First = ElementOfSecond;  

                continue;  
            }  

            return false;  
        }  

        return true;  
    }  
};

四.小結

這道題就是尋找一個好的數據結構來保存兩個string之間的字符的對應關系，根據這道題的假設，選擇數組是一個比較的解決方案。