Word_Ladder.png

/**
* Abstract: Actually if we take the words in the list as nodes, by 
* applying the rule of transformation we get a graph such that 
* every edge maps to a legal transition between its
* two vertices. And the problem here becomes a graph's single-source
* shortest path problem, which, can be solved by BFS.
* Reference: Algorithms, 4ed, by Robert Sedgewick&Kevin Wayne
*/
typedef struct QueueStruct {
    int *items, head, tail;
}*Queue;

Queue QueueCreate(int capacity) {
    Queue queue = (Queue)malloc(sizeof(*queue));
    queue->items = (int*)malloc(capacity * sizeof(int));
    queue->tail = queue->head = 0;
    return queue;
}

void QueueEnqueue(Queue queue, int item) { queue->items[queue->head++] = item; }

int QueueDequeue(Queue queue) { return queue->items[queue->tail++]; }

bool QueueIsEmpty(Queue queue) { return queue->head == queue->tail; }

typedef struct QLNodeStrcut {
    Queue queue;
    struct QNodeStrcut *next;
}*QLNode;

QLNode QLNodeCreate(Queue queue) {
    QLNode x = (QLNode)malloc(sizeof(*x));
    x->queue = queue;
    x->next = NULL;
    return x;
}

void bfs(int **table, int n, int *tableSize, int target, int *edgeTo, int qsize) {
    bool *marked = (bool*)malloc(n * sizeof(*marked));
    marked[0] = true;
    for (int i = 1; i < n; i++) { marked[i] = false; }
    Queue queue = QueueCreate(qsize);
    QueueEnqueue(queue, 0);
    do {
        int v = QueueDequeue(queue);
        int *adj = table[v];
        int adjn = tableSize[v];
        for (int i = 0; i < adjn; i++) {
            int w = adj[i];
            if (!marked[w]) {
                marked[w] = true;
                edgeTo[w] = v;
                QueueEnqueue(queue, w);
            }
        }
    } while (!QueueIsEmpty(queue));
}

bool diff(char *key, char *word) {
    size_t diff = 0, n = strlen(key), i = 0;
    while (i < n && diff <= 1) {
        if (key[i] != word[i]) { diff++; }
        i++;
    }
    return diff == 1;
}

int ladderLength(char * beginWord, char * endWord, char ** wordList, int wordListSize) {
    bool *blackList = (bool*)malloc(wordListSize * sizeof(*blackList));
    for (int i = 0; i < wordListSize; i++) { blackList[i] = false; }
    bool notFound = true;
    int target = 0;
    for (int i = 0; i < wordListSize; i++) {
        if (strcmp(endWord, wordList[i]) == 0) {
            notFound = false;
            target = i + 1;
            break;
        }
        if (strcmp(beginWord, wordList[i]) == 0) { blackList[i] = true; }
    }

    if (notFound) { return 0; }

    int **table = (int**)malloc((wordListSize + 1) * sizeof(*table));
    int *tableSize = (int*)malloc((wordListSize + 1) * sizeof(*tableSize));
    for (int i = 0; i <= wordListSize; i++) { 
        table[i] = (int*)malloc(wordListSize * sizeof(int)); 
        tableSize[i] = 0;
    }
    
    //Build table
    for (int i = 0; i < wordListSize; i++) {
        if (diff(beginWord, wordList[i])) { 
            table[0][tableSize[0]++] = i + 1;
            table[i + 1][tableSize[i + 1]++] = 0;
        } 
    }
    for (int i = 0; (i < wordListSize); i++) { if (!blackList[i]) { for (int j = 0; j < wordListSize; j++) { if ((j != i) && !blackList[j] && diff(wordList[i], wordList[j])) { table[i + 1][tableSize[i + 1]++] = j + 1; } } } }
    
    int qsize = 0;
    for (int i = 0; i <= wordListSize; i++) { qsize += tableSize[i]; }
    if (qsize == 0) { qsize = wordListSize + 1; }
    int *edgeTo = (int*)malloc((wordListSize + 1) * sizeof(*edgeTo));
    bfs(table, wordListSize + 1, tableSize, target, edgeTo, qsize);
    int min = 0;
    for (int v = target; v != 0; v = edgeTo[v]) { 
        if (v >= 0 && v <= wordListSize) {
            min++; 
        } else {
            min = INT_MAX;
            break;
        }
    }
    if (min == INT_MAX) { return 0; }
    return min + 1;
}