# Leetcode Word Ladder problem solution

In this Leetcode Word Ladder problem solution we have 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.

## Problem solution in Python.

```class Solution:
def helper(self,word1,word2):
not_same = 0
for i in range(len(word1)):
if word1[i] != word2[i]:
not_same += 1
if not_same > 1:
return False
if not_same == 1:
return True
else:
return False

def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
queue = []
visited = dict()
times = 1
queue.append((times,endWord))
while queue:
times,vertex = queue.pop(0)
visited[vertex] = vertex
if self.helper(beginWord,vertex):
return times+1
for x in wordList:
if self.helper(x,vertex) and x not in visited :
queue.append((times+1,x))
#print(x)
return 0
```

## Problem solution in Java.

```Set<String> dict = new HashSet<>(wordList);
if(!wordList.contains(endWord)) return 0;
int level = 0;
q.offer(beginWord);
while(q.size() > 0) {
int size = q.size();
while(size-- > 0) {
String curr = q.poll();
if(curr.equals(endWord)) return level+1;
for(int i=0; i<curr.length(); i++){
char[] arr = curr.toCharArray();
for(char c='a'; c<='z'; c++) {
if(c == curr.charAt(i)) continue;
arr[i] = c;
String next = new String(arr);
if(dict.contains(next)) {
q.offer(next);
dict.remove(next);
}
}
}
}
level++;
}

return 0;
```

## Problem solution in C++.

```class Solution {
public:
bool oneDiff(string a, string b){
int count = 0;
for(int i = 0; i < a.size(); i++){
if(a[i] != b[i])    count++;
if(count > 1)   return false;
}
if(count == 1)  return true;
else    return false;
}

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if(find(wordList.begin(), wordList.end(), endWord) == wordList.end())   return 0;
queue<string> bfs;
queue<string> temp;
int lvl = 1;
bfs.push(endWord);
remove(wordList.begin(), wordList.end(), endWord);

while(!bfs.empty()){
string s = bfs.front(); bfs.pop();
if(oneDiff(beginWord, s))   return lvl+1;
for(auto& str : wordList){
if(oneDiff(str, s)) {
temp.push(str);
remove(wordList.begin(), wordList.end(), str);
}
}

if(bfs.empty()){
if(!temp.empty()) lvl++;
while(!temp.empty()){
string ts = temp.front(); temp.pop();
bfs.push(ts);
}
}
}
return 0;
}
};
```

## Problem solution in C.

```#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

typedef struct {
char *word;
int level;
} node;
typedef struct {
node  *q;
int tail;
} q_t;

int one_diff(char *a, char *b) {
int diff = 0;
while (*a && diff <= 1) {
diff += (*a != *b) ? 1 : 0;
a ++; b ++;
}
return diff == 1 ? 1 : 0;
}

int bfs(q_t *q, char *end, char **dict, int sz, int *v) {
int i, d;
char *a, *b;

q->tail++;
a = q->q[q->tail].word;
d = q->q[q->tail].level;
for (i=0; i<sz ; i++) {
if (!v[i]) {
b = dict[i];
if (one_diff(a,b)) {
if (!strcmp(b, end)) {
return (d+1);
}
v[i] = 1;
}
}
}
}
return 0;
}
int ladderLength(char* beginWord, char* endWord, char** wordList, int wordListSize) {
q_t q;
int *v = calloc(wordListSize, sizeof(int));
int count;
if (!beginWord || !endWord || wordListSize <=0) {
return 0;
}
q.q = calloc(wordListSize+1, sizeof(node));