Word Ladder Leetcode optimised 2 solutions c++ code and explanation
Vložit
- čas přidán 6. 09. 2024
- A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord
Every adjacent pair of words differs by a single letter.
Every si is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
First thing when I come across questions ..I go through your playlist if not found then search elsewhere.....I really appreciate the way you explain
exactly doing the same
your explanation is amazing mostly your way to explain code with the help of example
✌✌
THANK YOU so much for your clear and DETAIL explanation!
Too good 🔥 explaination....clearly understood 👍👍
Nice explaination...
BeginWord could be added to vector at starting itself before creating Adj list
thank you, as always your explanation is great!
Keep it up ma'am ❤️❤️
Your explanation to good.
Nice explanation! Thanks
Nice explanation alli
you explain very well
Nice explanation Di❤
thank you so much
Thanks
Hey alisha cover some dp questions too if possible
can someone explain why time complexity is O(m*m*n) and not O(m*n) ?? it seems there are only 2 nested loops right?
(first loop -> n)*( second loop -> m)*( diff function is called (which traverse the word)-> size of word)
n*m* size of word
great explanation, could you please share the code?
😍😍
if possible, can you please share your code
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector& wordList) {
if (count(wordList.begin(), wordList.end(), endWord) == 0) return 0;
unordered_set Set;
queue Queue;
unordered_map Map;
wordList.push_back(beginWord);
int N = wordList.size(), M = beginWord.size();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
string x = wordList[i].substr(0, j) + '*' + wordList[i].substr(j + 1, M - j - 1);
Map[x].push_back(wordList[i]);
}
}
Queue.push({beginWord, 1});
while (!Queue.empty()) {
pair P = Queue.front();
Queue.pop();
for (int j = 0; j < M; j++) {
string x = P.first.substr(0, j) + '*' + P.first.substr(j + 1, M - j - 1);
for (string &word: Map[x]) {
if (Set.find(word) != Set.end()) continue;
if (word == endWord) return P.second + 1;
Queue.push({word, P.second + 1});
Set.insert(word);
}
}
}
return 0;
}
};
hello, can you make videos for DSA?
how can contact you?
probabilityisfun63@gmail.com