LeetCode 1153: String Transforms Into Another String Solution

Master LeetCode problem 1153 (String Transforms Into Another String), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1153. String Transforms Into Another String

Hard

Hash Table String

Problem Explanation

Explanation:

Given two strings str1 and str2, we need to determine if it is possible to transform str1 into str2 by performing the following operations:

Replace any character in str1 with any other lowercase English alphabet character.
Transform str1 into str2.

To solve this problem, we can use a mapping to keep track of the characters that have been replaced. We need to ensure that each character in str1 maps to only one character in str2.

Algorithmic Idea:

If the lengths of str1 and str2 are not equal, return false, as it is impossible to transform str1 into str2.
Create a mapping to store the character replacements from str1 to str2.
Iterate through each character in str1 and str2.
If the character in str1 is already mapped to a different character in str2, return false.
If the character in str1 is not mapped yet, add it to the mapping.
After processing all characters, if the size of the mapping is less than 26 (the number of lowercase English alphabet characters), return true.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the length of the input strings str1 and str2.

Space Complexity:

The space complexity of this algorithm is O(26) = O(1) since the mapping can have at most 26 entries.

Solution Code

class Solution {
    public boolean canConvert(String str1, String str2) {
        if (str1.equals(str2)) {
            return true;
        }
        
        Map<Character, Character> mapping = new HashMap<>();
        for (int i = 0; i < str1.length(); i++) {
            char c1 = str1.charAt(i);
            char c2 = str2.charAt(i);
            
            if (mapping.containsKey(c1) && mapping.get(c1) != c2) {
                return false;
            }
            
            mapping.put(c1, c2);
        }
        
        return new HashSet<Character>(mapping.values()).size() < 26;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1153 (String Transforms Into Another String)?

This page provides optimized solutions for LeetCode problem 1153 (String Transforms Into Another String) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1153 (String Transforms Into Another String)?

The time complexity for LeetCode 1153 (String Transforms Into Another String) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1153 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1153 in Java, C++, or Python.

Back to LeetCode Solutions