String Transforms Into Another String — LeetCode 1153 Python Solution
HardLeetCode PremiumGraphHash TableString
- Problem
- #1153
- Pattern
- Depth-First Search
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
Python
class Solution:
def canConvert(self, str1: str, str2: str) -> bool:
if str1 == str2:
return True
if len(set(str2)) == 26:
return False
d = {}
for a, b in zip(str1, str2):
if a not in d:
d[a] = b
elif d[a] != b:
return False
return TrueComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(C) auxiliary |
Pattern: Depth-First Search
Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 1153. String Transforms Into Another String is filed here because LeetCode tags it Graph, which is the vocabulary this hub collects.
The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.
Related problems
LeetCode 2115Find All Possible Recipes from Given SuppliesMediumLeetCode 1156Swap For Longest Repeated Character SubstringMediumLeetCode 1160Find Words That Can Be Formed by CharactersEasyLeetCode 3Longest Substring Without Repeating CharactersMediumLeetCode 12Integer to RomanMediumLeetCode 13Roman to IntegerEasy
Frequently asked questions
- How hard is LeetCode 1153. String Transforms Into Another String?
- LeetCode 1153. String Transforms Into Another String is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1153. String Transforms Into Another String?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1153. String Transforms Into Another String?
- The Python solution on this page uses O(C) auxiliary space.
- What topics does LeetCode 1153. String Transforms Into Another String cover?
- LeetCode 1153. String Transforms Into Another String is tagged Graph, Hash Table and String on LeetCode.
- Is LeetCode 1153. String Transforms Into Another String a premium problem?
- Yes. LeetCode 1153. String Transforms Into Another String is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.