LeetCode_Isomorphic Strings

时间：2015-05-18 10:56:22 收藏：0 阅读：241

一.题目

Isomorphic Strings

Total Accepted: 8671 Total Submissions: 36190My Submissions

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.

Show Tags

Have you met this question in a real interview?

Yes

Discuss

二.解题技巧

这道题主要是建立两个字符串中不同字符的对应关系，由于ASCII编码的字符只有256个，而且string中是不保存null字符的，因此，可以建立两个大小为256的字符数组来保存两个string中每一个字符在另外一个string中的对应的关系，然后遍历string中的每一个字符，如果相同位置的字符是互相对应的话，就处理下一个字符，如果不是互相对应的话，就在说明这两个string不是同等结构的。

也可以通过两个map来实现，但是map的查找过程时间复杂度为O(lgn)，但是上面对于string中的每一个字符串都需要查找，因此，使用map的话，时间复杂度太高了。也可以使用hash表来做，也就是使用unordered_map来实现，但是由于ASCII编码的字符的个数是固定的而且个数比较少，使用数组完全可以很好地实现。

三.实现代码

#include <string>
#include <vector>

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

class Solution
{
public:
    bool isIsomorphic(string s, string t)
    {
        vector<unsigned char> First(256, 0);
        vector<unsigned char> 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之间的字符的对应关系，根据这道题的假设，选择数组是一个比较的解决方案。

原文：http://blog.csdn.net/sheng_ai/article/details/45815515