52 lines
1.6 KiB
Markdown
52 lines
1.6 KiB
Markdown
# 17.14. Word transformer
|
|
|
|
## Given two words of equal lengths that are in the dictionary, transform one word into another word by changing only one letter at a time. The new word you get in each step must be in the dictionary
|
|
|
|
I guess we have to return the number of steps?
|
|
|
|
> example: input: "DAMP", "LIKE"
|
|
> "DAMP" -> "LAMP" -> "LIMP" -> "LIME" -> "LIKE"
|
|
|
|
## Initial scenario
|
|
|
|
Only len(s) changes must be done. Iterate through s1, see if `s1[:i] + s2[i] + s1[i:]` is present in `dct`, if so change and update boolean array. If not, `i+1`.
|
|
|
|
```python
|
|
dct = ["damp", "lamp", "limp", "lime", "like"]
|
|
|
|
def transform(s1, s2):
|
|
|
|
if len(s1) != len(s2):
|
|
return -1
|
|
|
|
n = len(s1)
|
|
found = [0] * n
|
|
steps = 0
|
|
for i in range(n):
|
|
pos_s = s1[:i] + s2[i] + s1[i+1:]
|
|
if pos_s in dct and not found[i]:
|
|
s1 = pos_s
|
|
found[i] = 1
|
|
steps += 1
|
|
|
|
for i in range(n):
|
|
if found[i]:
|
|
continue
|
|
pos_s = s1[:i] + s2[i] + s1[i+1:]
|
|
if pos_s in dct:
|
|
s1 = pos_s
|
|
found[i] = 1
|
|
steps += 1
|
|
|
|
return steps
|
|
```
|
|
|
|
This takes O(2n) time and O(n) space. Not bad for a start, let's think of more complicated examples.
|
|
|
|
## More complicated examples
|
|
|
|
What if we need a temporary random letter not present in s1 or s2? No direct transformations?
|
|
|
|
> "damp" -> "kamp" -> "kalp" -> "malp"
|
|
|
|
The only transformation from "**m**amp" is "kamp", which doesn't necessarily bring us closer to our second string. This looks like a graph/shortest path algorithm, no idea how to tackle this as of 9 may 2019. |