Word ladder I
Apple
LinkedinThe problem
Given are the two distinct words startWord and targetWord, and a list of size N, denoting wordList of unique words of equal size M. Find the length of the shortest transformation sequence from startWord to targetWord.
Keep the following conditions in mind:
- A word can only consist of lowercase characters.
- Only one letter can be changed in each transformation.
- Each transformed word must exist in the wordList including the targetWord.
- startWord may or may not be part of the wordList
Note: If there’s no possible way to transform the sequence from startWord to targetWord return 0.
Input: wordList = ["des","der","dfr","dgt","dfs"], startWord = "der", targetWord = "dfs" Output: 3 Explanation:
- The length of the smallest transformation sequence from "der" to "dfs" is 3
- i.e. "der" -> (replace ‘e’ by ‘f’) -> "dfr" -> (replace ‘r’ by ‘s’) -> "dfs".
- So, it takes 3 different strings for us to reach the targetWord. Each of these strings are present in the wordList.
Input: wordList = ["geek", "gefk"], startWord = "gedk", targetWord= "geek" Output: 2 Explanation:
- The length of the smallest transformation sequence from "gedk" to "geek" is 2
- i.e. "gedk" -> (replace ‘d’ by ‘e’) -> "geek" .
- So, it takes 2 different strings for us to reach the targetWord. Each of these strings are present in the wordList.
Input: wordList = ["hot", "dot", "dog", "lot", "log"], startWord = "hit", targetWord = "cog"
- 1 ≤ wordList.length ≤ 100
- 1 ≤ wordList[i].length ≤ 10
- startWord.length == targetWord.length == wordList[i].length
- startWord, targetWord, and wordList[i] consist of lowercase English letters.
- startWord!= targetWord
cpp
class Solution{
public:
int wordLadderLength(string startWord, string targetWord,
vector<string> &wordList) {
}
};java
class Solution {
public int wordLadderLength(String startWord, String targetWord, List<String> wordList) {
}
}python
class Solution:
def wordLadderLength(self, startWord, targetWord, wordList):javascript
class Solution {
wordLadderLength(startWord, targetWord, wordList) {
}
}csharp
public class Solution
{
public int WordLadderLength(string startWord, string targetWord, List<string> wordList)
{
}
}go
func wordLadderLength(startWord string, targetWord string, wordList []string) int {
}Stuck? Show a way to structure it+
- 01Clarify whether endpoints count in the length
- 02Put dictionary words in a hash set
- 03BFS by levels, generating one-letter mutations
- 04Return on reaching target or zero if exhausted
Reference answer
Then expect these follow-ups
How can bidirectional BFS accelerate this?
Tests: follow-up reasoning
How do you handle a target absent from the dictionary?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question