http://leetcode.liangjiateng.cn/leetcode/string-transforms-into-another-string/
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.
Note:
1 <= str1.length == str2.length <= 10^4- Both
str1andstr2contain only lowercase English letters
给出两个长度相同的字符串，分别是
str1 和 str2。请你帮忙判断字符串 str1 能不能在 零次 或 多次 转化后变成字符串 str2。
每一次转化时，将会一次性将
str1 中出现的 所有 相同字母变成其他 任何 小写英文字母（见示例）。
只有在字符串
str1 能够通过上述方式顺利转化为字符串 str2 时才能返回 True，否则返回 False。
示例 1：
示例 2：
提示：
1 <= str1.length == str2.length <= 10^4str1和str2中都只会出现 小写英文字母
转化的定义: 一次性将字符串中出现的 所有 相同字母变成其他 任何 小写英文字母例如:aabcc --> ccbcc(a转化成c) --> eebee(c转化成e)
由上图可以看出:
转化的真正意义是 多对一映射 如此可以得出以下判断依据:
转化的真正意义是 多对一映射 如此可以得出以下判断依据:
- 判断依据一: 字符种类
转化后的字符种类必定小于或者刚好等于转化前的字符种类
注意:这种映射是有限制的, 它只能转化成小写字母, 即它只能在26个小写字母之间转化,
所以目标字符串的字符种类不能为26(满值), 除非两字符串相等, 否则必定无法转化 - 判断依据二: 映射表
可以建立映射表, 查看是否为多对一的映射
代码实现
- 使用两个HashMap来构建映射表
使用两个HashMap来构建映射表
class Solution {
public boolean canConvert(String str1, String str2) {
if (null == str1 | null == str2) return false;
// 两字符串长度不一必定无法转化
if (str1.length() != str2.length()) return false;
// 两字符串相等 无需转化
if (str1.equals(str2)) return true;
// 求元素种类
HashSet<Character> set = new HashSet<>();
for (char c : str1.toCharArray()) set.add(c);
int size1 = set.size();
set.clear();
for (char c : str2.toCharArray()) set.add(c);
int size2 = set.size();
// 转换字符串str2元素种类满26 必定无法转化
// 转化后字符串元素种类比转化前还多
if (size2 == 26 | size1 < size2) return false;
// 建立映射表
// str1ToStr2 存放被转化字符串的字符及其转化后字符所对应的标识label 字符 -> label 多对一
HashMap<Character, Integer> str1ToStr2 = new HashMap<>();
// str2Table 存放转化后字符所对应的标识label 字符 -> label 一对一
HashMap<Character, Integer> str2Table = new HashMap<>();
// label 转化后字符所对应的标识label
int label = 0;
// 遍历字符
char c1, c2;
for (int i = 0; i < str1.length(); i++) {
c1 = str1.charAt(i);
c2 = str2.charAt(i);
// c1 --> c2
// c2没有被标识
if (!str2Table.containsKey(c2)) {
// c1已经有转化对应字符了 c1!->c2 多对多
if (str1ToStr2.containsKey(c1)) return false;
// c1 -> label
str1ToStr2.put(c1, label);
// c2 -> label
str2Table.put(c2, label);
label++;
}
// c2已经被标识 c1没有被标识(还没有确定转化字符)
if (!str1ToStr2.containsKey(c1)) {
// c1 -> label -> c2
str1ToStr2.put(c1, str2Table.get(c2));
}
// c1,c2都已经被标识 查看两者标识是否相同
// c1 -> label ?-> c2
if (str1ToStr2.get(c1) != str2Table.get(c2)) {
return false;
}
}
return true;
}
}- 使用数组来构建映射表
使用数组来构建映射表
class Solution {
public boolean canConvert(String str1, String str2) {
if (null == str1 | null == str2) return false;
// 两字符串长度不一必定无法转化
if (str1.length() != str2.length()) return false;
// 两字符串相等 无需转化
if (str1.equals(str2)) return true;
// 求元素种类
int n = str1.length(), size1 = 0, size2 = 0, p = 0, q = 0;
boolean[] v1 = new boolean[30];
boolean[] v2 = new boolean[30];
for (int i = 0; i < n; i++) {
p = str1.charAt(i) - 'a';
q = str2.charAt(i) - 'a';
if (!v1[p]) {
size1++;
v1[p]=true;
}
if (!v2[q]) {
size2++;
v2[q]=true;
}
}
// 转换字符串str2元素种类满26 必定无法转化
// 转化后字符串元素种类比转化前还多
if (size2 == 26 | size1 < size2) return false;
// 建立映射表
// s1ToS2 映射表 下标表示原字符-'a' 值表示目标字符
char[] s1ToS2 = new char[30];
char c = '#';
// 映射表初始化为全'#'
for (int i = 0; i < 26; i++) s1ToS2[i] = '#';
for (int i = 0; i < n; i++) {
p = str1.charAt(i) - 'a';
c = str2.charAt(i);
// 该字符p还没有映射
// 或者
// 该字符p映射已经映射 且映射单一
if (s1ToS2[p] == '#' | s1ToS2[p] == c) s1ToS2[p]=c;
else return false;
}
return true;
}
}
遍歷一遍str1，就知道str1的每個字符應該映射到誰了
但是1個字符不能映射到2個字符 同時
此外，如果
但是1個字符不能映射到2個字符 同時
str1裏的字符個數應該少於str2裏的字符個數此外，如果
str2有26個字符時，除非兩個字符串相等，否則不可能轉化成功，因爲str1此時也得有26個字符，但是不管動了哪個字符，映射完之後就只有25個字符了，這時候無法再映射回26個字符 def canConvert(self, str1: str, str2: str) -> bool:
have = set()
change = {}
n = len(str1)
for i in range(n):
have.add(str2[i])
if str1[i] not in change:
change[str1[i]] = str2[i]
if change[str1[i]] != str2[i]:
return False
return len(change)>=len(have) and (len(have)<26 or str1==str2)