程序员人生网站导航

[LeetCode] Isomorphic Strings

栏目：php教程时间：2015-05-08 08:33:02

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;
}

------分隔线----------------------------

上一篇 Java Notes-10

下一篇 算法荐书（程序员练功+大众科普）

------分隔线----------------------------