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
Hiring now
Linkedin has 196 open roles right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Software Engineer - Systems and Infrastructure
Mountain View, CA, United States
Lead Account Executive, Large Customer, Financial Services - LinkedIn Marketing Solutions
Chicago, IL, United States
Director, LinkedIn Pulse Digital Platform
New York, NY, United States
Next question