LeetCode: 205. 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.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Note:

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

解题思路

根据字符出现的顺序对当前字符串的字符进行编号。如果两个字符的编号序列一致，则它们是同构(Isomorphic)字符串。

AC 代码

class Solution {
    string getPattern(string str)
    {
        unordered_map<char, char> ch2Idx;
        string pattern;
        
        for(char ch : str)
        {
            auto iter = ch2Idx.find(ch);
            if(iter == ch2Idx.end())
            {
                // 根据字符出现顺序，对字符进行编号
                ch2Idx[ch] = ch2Idx.size() + '0';
                iter = ch2Idx.find(ch);
            }
            
            pattern.push_back(iter->second);
        }
        
        return pattern;
    }
public:
    bool isIsomorphic(string s, string t) {
        return (getPattern(s) == getPattern(t));
    }
};