1 题目
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.2 尝试解
2.1 分析
给定两个字符串S1和S2，给定一种变化操作，可以将S1中某一字符全部变为另一种字符。问经过若干次变化后，S1能否变成S2。
直觉要用map，将S1中的每一个字符映射到S2中对应位置的字符。如果S1中有相同的字符映射到了不同的字符上，那如何变化都不能成功。如果没有冲突，再考虑变幻操作。
如果只有3种合法字符a,b,c，S1=abc，S2=bca。那么对S1中任何字符的变化都会使相同字符映射到不同的字符上。
但是如果有4种合法字符a,b,c,d，S1=abc，S2=bca，如果要对a进行变化，可以在S1中，先将a映射后会冲突的字符，即b变化为d（如下操作第二步），然后进行变化（第三步）。然后将d还原为上一步映射的原字符（第四步）。重复上述操作。
S1 abc → adc → bdc → bac
S2 bca → bca → bca → bca
所以只要有未使用的合法字符，就可以完成变幻。一种情况是size(map)<26，就仍有映射的合法字符。再考虑两种字符映射到同一种字符，如a→z，b→z。可以先将b全部变化为a，那么就空出来一种合法字符b。所以size(set(map.values()))<26也可以完成转换。而且第一种情况是第二种情况的子集。
2.2 代码
class Solution { public: bool canConvert(string str1, string str2) { if(str1 == str2) return true; map<char,char> convertion,anticonvertion; //If same char in str1 maps to different char in str2, there is no solution for(int i = 0; i < str1.size(); i++){ if(convertion.count(str1[i])!=0 && convertion[str1[i]]!=str2[i]) return false; convertion[str1[i]] = str2[i]; anticonvertion[str2[i]] = str1[i]; } //If there is any char not appearing in str1,there is a solution. If there is two char like a and b in str1 maps to same char in str2, we can convertion b to a. So b is not appearing now. if(convertion.size()<26 || convertion.size() > anticonvertion.size()) return true; else return false; } };3 标准解
class Solution { public: bool canConvert(string s1, string s2) { if (s1 == s2) return true; unordered_map<char, char> dp; for (int i = 0; i < s1.length(); ++i) { if (dp[s1[i]] != NULL && dp[s1[i]] != s2[i]) return false; dp[s1[i]] = s2[i]; } return set(s2.begin(), s2.end()).size() < 26; } };
