1153. String Transforms Into Another String π
Description
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.
Constraints:
1 <= str1.length == str2.length <= 104
str1
andstr2
contain only lowercase English letters.
Solutions
Solution 1: Hash Table
First, we can check if str1
and str2
are equal. If they are, return true
directly.
Then we count the occurrence of each letter in str2
. If the occurrence equals $26$, it means str2
contains all lowercase letters. In this case, no matter how str1
is transformed, it cannot become str2
, so return false
directly.
Otherwise, we use an array or hash table d
to record the letter each letter in str1
is transformed to. We traverse the strings str1
and str2
. If a letter in str1
has been transformed, the transformed letter must be the same as the corresponding letter in str2
, otherwise return false
.
After the traversal, return true
.
The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ is the length of the string str1
, and $C$ is the size of the character set. In this problem, $C = 26$.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|