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;
        Queue<String> q = new LinkedList<>();
        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 head;
    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;
    
    while(q->head != q->tail) {
        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);
                    }
                    q->head++;
                    q->q[q->head].word = b;
                    q->q[q->head].level = 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));
    q.head = q.tail = -1;
    q.head++;
    q.q[q.head].word = beginWord;
    q.q[q.head].level = 1;
    count = bfs(&q, endWord, wordList, wordListSize, v);
    free(q.q);
    free(v);
    return count;
}