
Problem Statement
Given two strings, str1
and str2
, both of identical length, determine whether it is possible to transform str1
into str2
through a series of character conversions. Each conversion allows changing all occurrences of one specific character in str1
to any other lowercase English letter.
Return true
if it is possible to make str1
equal to str2
through such transformations, otherwise return false
.
Examples
Example 1
Input:
str1 = "aabcc" str2 = "ccdee"
Output:
true
Explanation:
Convert 'c' → 'e', then 'b' → 'd', then 'a' → 'c'. The order of conversions matters.
Example 2
Input:
str1 = "vultrcore" str2 = "corevultr"
Output:
false
Explanation:
There is no way to transform str1 to str2 without causing conflicting character mappings.
Constraints
1 <= str1.length == str2.length <= 10^4
str1
andstr2
consist of lowercase English letters only.
Approach and Intuition
To determine if the transformation is possible:
Consistent Mapping:
- Each character in
str1
must always map to the same character instr2
. - If a character maps to multiple targets, return
false
.
- Each character in
One-to-One Validity:
- Ensure that two different characters from
str1
don't map to the same target instr2
, unless that’s unavoidable and a cycle can be broken.
- Ensure that two different characters from
Cycle Handling:
- If all 26 lowercase characters are already in use in
str2
, a cycle in the mapping cannot be resolved (since there is no temporary character left to assist), and the transformation is impossible.
- If all 26 lowercase characters are already in use in
Quick Return:
- If
str1 == str2
, returntrue
immediately, as no conversion is needed.
- If
This strategy ensures correctness while adhering to the transformation rules, even in edge cases involving cycles or tight letter constraints.
Solutions
- C++
- Java
- Python
class Solution {
public:
bool isTransformable(string s1, string s2) {
if (s1 == s2) {
return true;
}
unordered_map<char, char> mapChar;
unordered_set<char> s2Chars;
for (int i = 0; i < s1.length(); i++) {
if (mapChar.find(s1[i]) == mapChar.end()) {
mapChar[s1[i]] = s2[i];
s2Chars.insert(s2[i]);
} else if (mapChar[s1[i]] != s2[i]) {
return false;
}
}
if (s2Chars.size() < 26) {
return true;
}
return false;
}
};
This solution checks if one string s1
can be transformed into another string s2
by mapping each character of s1
to characters in s2
. The C++ code defines a method isTransformable
which returns a boolean indicating whether the transformation is possible. Here's a breakdown of the code:
- Initialize a
mapChar
to track mappings from characters ins1
tos2
, and as2Chars
set to collect the unique characters ins2
. - If
s1
is identical tos2
, returntrue
immediately. - Iterate over characters of
s1
:- If the character from
s1
has not been mapped, map it to the corresponding character ins2
and add the character froms2
to the set. - If the character mapping is inconsistent (a character maps to multiple characters), return
false
.
- If the character from
- After the loop, if the size of the
s2Chars
set is less than 26 (total number of English alphabet letters), returntrue
. This implies there is at least one character ins2
that is not being used and can potentially be used for transformation if needed. - If every character in the alphabet is used in
s2
, returnfalse
as the transformation might not be possible due to inability to use characters ins1
that need new mappings to unused characters ins2
.
This logic ensures that transformation is possible if characters in s1
either map to themselves in s2
or have consistent mappings without exhausting all possible characters (allowing for necessary transformations).
class Solution {
public boolean isConvertible(String original, String target) {
if (original.equals(target)) {
return true;
}
HashMap<Character, Character> map = new HashMap<>();
HashSet<Character> usedCharacters = new HashSet<>();
for (int index = 0; index < original.length(); index++) {
char origChar = original.charAt(index);
char targetChar = target.charAt(index);
if (!map.containsKey(origChar)) {
map.put(origChar, targetChar);
usedCharacters.add(targetChar);
} else if (map.get(origChar) != targetChar) {
return false;
}
}
return usedCharacters.size() < 26;
}
}
This Java solution explores the transformation possibility of one string into another by mapping each character from the original string to a corresponding character in the target string. Follow this solution summary to understand how each character mapping and condition contributes to assessing the transformativeness:
- Start by checking if the original string equals the target string, in which case, return true because no transformation is needed.
- Initialize a HashMap (map) to associate characters from the original string to the target string, and a HashSet (usedCharacters) to keep track of all characters already used in the transformation.
- Loop through each character of the original string:
- If the current original character is not yet mapped, add it to the map with its corresponding character from the target string. Also, add this target character to the set of used characters.
- If the current original character is already mapped, check if it maps to the same target character. If not, return false, indicating that a transformation is not possible due to conflicting mappings.
- Check the size of the usedCharacters set. If there are 25 or fewer characters, transformation is possible because there is room to maneuver a character if needed. Return true if possible, otherwise false.
The solution's efficiency lies in its ability to quickly determine transformation feasibility using character mapping and set operations, ensuring that each character has a unique transformation unless they are being reused effectively.
class Transformation:
def canTransform(self, s1: str, s2: str) -> bool:
if s1 == s2:
return True
mapping_dict = {}
unique_chars_in_s2 = set()
for ch1, ch2 in zip(s1, s2):
if ch1 not in mapping_dict:
mapping_dict[ch1] = ch2
unique_chars_in_s2.add(ch2)
elif mapping_dict[ch1] != ch2:
return False
return len(unique_chars_in_s2) < 26
In this solution, the given Python function canTransform
checks if it is possible to transform one string, s1
, into another string, s2
, using a character-by-character mapping without any two characters in s1
being mapped to the same character in s2
unless they are identical.
Key details in the solution:
- Handle the immediate case where the two strings are identical. in such a scenario, return True since no transformation is needed.
- Utilize a dictionary
mapping_dict
to maintain the mappings froms1
tos2
. - Use a set
unique_chars_in_s2
to track all unique characters that have been mapped to froms1
. - Iterate over pairs of characters from
s1
ands2
simultaneously:- if a character from
s1
has not been mapped yet, map it and add the corresponding character froms2
to the set of unique characters. - If there's already a mapping for a character, check if it conflicts with the new character from
s2
; if it does, the transformation is not possible, hence return False.
- if a character from
- Finally, ensure the total number of unique mapped characters in
s2
is less than 26. This is essential since the transformation can only occur if there is, at least, one character in the alphabet that has not been used ins2
, allowing for reversible transformations if necessary.
The function returns:
True
if the transformation is possible under the provided conditions.False
otherwise.
No comments yet.