please check my leetcode solution i am getting TLE on a test case .
code link: https://ide.codingblocks.com/s/278921
Leetcode Link:- https://leetcode.com/problems/word-ladder/
One test case is failed
You need to optimize your code/approach.
You can refer this
but how i have commented the code where is the possiblity to optimize but unable to think how to optimize it
Preparing an adjacency matrix is not required here. It is just making your code O(n^2)
Refer the approach which i have shared.
1 Like
could you please make your code more commented at i am having some difficulty in understanding it.
for(int i=0;i<len;i++)
{
string str=orig;
for(char ch=‘a’;ch<=‘z’;ch++)
{
if(str[i]==ch) continue;
str[i]=ch;
if(str==endWord) return (level+1);
if(st.find(str)!=st.end())
{
q.push(str);
st.erase(str);
}
}
}
If you are not able to understand the approach, refer this video https://www.youtube.com/watch?v=M9cVl4d0v04 Same approach has be explained
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
@pratyush63 please help me to understand the time complexity of this program because according to me tc of this program is more than the solution of proposed by me
There was no requirement of making an adjacency matrix. That was just an overhead to the time complexity. That might be the reason for your TLE
BFS is used here.
You can notice that each possible transition of string will be pushed and popped out of the queue only once.
@gaurav19063 check this
