[LeetCode] Isomorphic Strings

发布时间：2020-12-13 20:08:48 所属栏目：PHP教程来源：网络整理

导读：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 ch

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.

解题思路

建立两个表：
①从字符串s到字符串t的字符映照表，由于最大的字母为122，因此映照表的大小为123。映照表键值为s中的字符，value为t中对应位置的字符。
②isUsed表代表t中的该字符是不是已被作为s中某字符的value值。

实现代码

#include <iostream>
using namespace std;

//Runtime:12ms
class Solution {
public:
    bool isIsomorphic(string s,string t) {
        int len = s.size();
        unsigned char map[123] = {0};
        bool isUsed[123] = {0};
        for (int i = 0; i < s.size(); i++)
        {
            if (map[s[i]] == 0)
            {
                if (!isUsed[t[i]])
                {
                    map[s[i]] = t[i];
                    isUsed[t[i]] = true;
                }
                else
                {
                    return false;
                }
            }
            else if (map[s[i]] != t[i])
            {
                return false;
            }
        }

        return true;
    }
};

int main()
{
    Solution s;
    cout<<s.isIsomorphic("aba","baa")<<endl;
    cout<<s.isIsomorphic("egg","add")<<endl;
    cout<<s.isIsomorphic("foo","bar")<<endl;
    cout<<s.isIsomorphic("paper","title")<<endl;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!