LeetCode解题报告（451）-- 1153. String Transforms Into Another String

Problem

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:

1
2
3

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:

1
2
3

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

Constraints:

1 <= str1.length == str2.length <= 104
str1 and str2 contain only lowercase English letters.

Analysis

这道题目给出两个字符串str1和str2，定义conversion为把str1中某个字符全部替换成另一个字符，问是否能通过若干个conversion去使得str1 = str2。这里讨论的是映射，映射有多种，我们先来看怎么映射法：

str1中的字符一一对应映射到str2中的字符，这个是最简单的，例如abcd映射到wxyz；
str1中的字符一对多映射到str2中的字符，这个是不允许的，例如abab映射到wxyz，a无法同时映射到w和y；
str1中的字符串多对一映射到str2中的字符，这个是允许的，例如abcd映射到xxyy。

根据上面的分析，我们可以知道只有第二种映射是非法的，其余的情况都是可以成功转化。这里还需要处理一种情况，就是映射死循环。比如str1 = abcdefghijklmnopqrstuvwxyz，str2 = bcdefghijklmnopqrstuvwxyza ，这种情况下，虽然字符是一一对应，但是存在着循环，比如str1中的a映射到b，然后b又映射到c，那么前两个字符就会变成cc，而不是我们期望的bc。

因此，为了判断第二种条件，我们用一个map来记录映射关系即可，如果str1中的字符有多于两个映射，则return false；为了判断映射死循环，我们用一个set来记录在str2中被映射过的字符，如果26的个字符都被映射过，说明就是死循环了。

Solution

无。

Code

class Solution {
public:
    bool canConvert(string str1, string str2) {
        if (str1 == str2) {
            return true;
        }
        
        unordered_map<char, char> m;
        unordered_set<char> uniqueCharInStr2;
        
        int size = str1.size();
        for (int i = 0; i < size; ++i) {
            char ch1 = str1[i];
            char ch2 = str2[i];
            
            if (m.count(ch1) && m[ch1] != ch2) {
                return false;
            } else if (m.count(ch1) == 0) {
                m[ch1] = ch2;
                uniqueCharInStr2.insert(ch2);
            }
        }
        return uniqueCharInStr2.size() < 26;
    }
};

Summary

这道题目的难度主要在前期的分析上，要分析出映射的类型以及分析出哪些是非法的，哪些是合法的。处理映射类型的题目一般都会用map。这道题目的分享到这里，感谢你的支持！