Longest Word in Dictionary (LeetCode 720. Algorithm Explained)

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[rupaldesai]

One request, if implemented it will be appreciated. Can you give a quick review of time and space complexity by the end of each video?

[supratimbhattacharjee]

//This question can also be solved using Trie

class TrieNode {
public:
char data;
vector<TrieNode*> children;
bool isTerminal;

TrieNode(char data) {
this->data=data;
for(int i=0;i<26;i++) {
children.push_back(nullptr);
}
isTerminal=false;
}
};

class Trie {
private:
void insertHelper(TrieNode* node, string word, int index) {
if(index==word.size()) {
node->isTerminal=true;
return;
}

int childIndex=word[index]-'a';
{
TrieNode* child=new TrieNode(word[index]);

insertHelper(child, word, index+1);
} else {
insertHelper(node->children[childIndex], word, index+1);
}
}

bool searchHelper(TrieNode* node, string word, int index) {
if(index==word.size()) {
return node->isTerminal;
}
int childIndex=word[index]-'a';

return searchHelper(node->children[childIndex], word, index+1);
} else {
return false;
}
}

bool startsWithHelper(TrieNode* node, string prefix, int index) {
if(index==prefix.size()) {
return true;
}
int

return startsWithHelper(node->children[childIndex], prefix, index+1);
} else {
return false;
}
}
public:
TrieNode* root;

Trie() {
root=new TrieNode('X');
}

void insert(string word) {
insertHelper(root, word, 0);
}

bool search(string word) {
return searchHelper(root, word, 0);
}

bool startsWith(string prefix) {
return startsWithHelper(root, prefix, 0);
}
};

class Solution {
public:
string longestWord(vector<string>& words) {
Trie* trie=new Trie();
string ans="";
for(auto word: words) {
trie->insert(word);
}

for(auto word: words) {
int count=0;
TrieNode* node=trie->root;
for(int i=0;i<word.size();i++) {
char curChar=word[i];

count++;

}
if(count==word.size() && word.size()>=ans.size() && (word.size()>ans.size() || word<ans)) {
ans=word;
}
}

return ans;
}
};

[free-palestine]

Hey nick, can you give advice on how you got good at Leetcode? I have a lot of trouble doing problems n always end up having to look for an explanation and it makes me not want to do it anymore

[ramazanchasygov]

What is time and space complexity? Is it O(l * nlogn) where l is length of word and n is number of words, with space complexity O(l * n)?

[badrulhussain]

Hi, this question was on Trie so why are you not using Trie to solve it?

[vraih]

hey nick, I love your videos and I might have seen most of a request, can u please make a video on leetcode 410 Split Array Largest Sum ... Thanks :)

[mohitpunia]

This problem can be solved using O(1) space complexity. if you are doing sort, then why do you need hashmap? no need for that

[Nikita-xkfc]

Its not mentioned in the question anywhere that the character needs to be added at the end only.But this solution is applicable only if we are allowed to add a character at the end.Isn't it?Or m I missing something?
Also if, the word array lacks a word of length 1, then should the output be " "?

[praveenchouhan]

yes nice explaination, but the solution is incomplete without the running time and space analysis, request you to please include that in the description and ur

[balamukundam]

could u plz upload a solution using trie

[sudhamshuhosamane]

How does this work if the root string is not a single character?

[madhuvamsimachavarapu]

Can we do this with tries data structure? Although this is also a good solution.

[tracy_gao]

Nice approach, if don't use sort the time complexity should be liner.

[ajrze]

Nike, what was the difficulty of Google interview problems which you gave. Was it leetcode medium or hard.