题目描述

Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions.

In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

Return true if and only if you can transform str1 into str2.

样例

Example 1:

Input: str1 = "aabcc", str2 = "ccdee"
Output: true
Explanation: Convert 'c' to 'e' then 'b' to 'd' then 'a' to 'c'. Note that the order of conversions matter.
Example 2:

Input: str1 = "leetcode", str2 = "codeleet"
Output: false
Explanation: There is no way to transform str1 to str2.

算法1

(暴力枚举) $O(n)$

建hashmap对应str1和str2的每一个字符，如果发现对应不上的情况返回false。注意str2的不同字符数量应该小于26个。

时间复杂度

遍历一遍时间复杂度O（n）
新建一个hashmap空间复杂度O（n）

参考文献

C++ 代码

class Solution {
public:
    bool canConvert(string str1, string str2) {
        if(str1==str2) return true;
        unordered_map<int,int> m;
        for(int i=0;i<str1.size(); i++)
        {
            if(m[str1[i]]!=NULL && m[str1[i]]!=str2[i])
                return false;
            m[str1[i]]=str2[i];
        }
        return unordered_set<int>(str2.begin(), str2.end()).size()<26;
    }
};