String Transforms Into Another String - Leetcode Solution

Problem Statement: 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.

Approach: The problem can be solved using graph-based observations. Given two strings str1 and str2, if we cannot convert them using a sequence of letter conversions, return false. Else, it is possible to convert str1 to str2 using a sequence of letter conversions.

If str1 can be converted to str2, every occurrence of a character in str1 can be converted to the same character in str2. When the same character in str1 experience two or more conversions, i.e., from char1 to char2 and then from char2 to char3, it is equivalent to a single conversion from char1 to char3.

Consider the example, input: str1 = "aabcc", str2 = "ccdee". To convert string 1 to string 2, 'a' needs to be converted to 'c'. As 'c' occurs only in string1 and string2, all occurrences of 'c' can be replaced by 'e'. In a similar way, 'b' can be converted to 'd'.

Notice that string transforms will cyclically reduce the activation process. If we had no need to cycle back to a previously transformed character, the process is definitely allowed. Otherwise, we need to cycle between available and used characters in a way that prevents cycles longer than 2, i.e., A -> B -> A -> B is forbidden.

To determine if the input strings satisfy the constraints described above, we perform the following operations on str1 and str2:

• Keep track of the character transformations in a dictionary called char_map.
• If the value for a key (value of character in str1) in the char_map does not match the same character string, it is an invalid transformation. Return false.
• Cyclic mapping is allowed for unique characters. So, characters in str2 should be different from the keys in char_map. Else, we will get stuck in an infinite cycle. Return false.

Solution:

• Initialize an empty Python dictionary called char_map.
• Iterate over the characters in str1 and str2, and keep making transformations until we can convert str1 to str2.
• If a character in str1 is already mapped to a different character, return False as this is an invalid transformation.
• If a character in str1 is not mapped to another character yet, map it to the character in str2 that we want to convert it to.
• Check if we have not already converted the character in str2 to a different character, if it is not true then return False, else it is a valid transformation.
• If all characters can be accurately transformed, return True.

Time Complexity : O(n) Space Complexity : O(n)

Python Code:

1