WL_2.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
*/

/**
* The queue here is impled array-basedly. A linked list version
* is used in previous submissions and it works as well, which,
* as a advantage over the array-based version here, eliminates the
* need of calculating the qsize(and the somewhat awkward corner case
* handling for when qsize equaling zero by assigning it wordListSize
* + 1: if (qsize == 0) { qsize = wordListSize + 1; })
*/
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 PLNodeStrcut {
    int *path;
    int n;
    struct PLNodeStrcut *next;
}*PLNode;

PLNode PLNodeCreate(int *path, int n) {
    PLNode x = (PLNode)malloc(sizeof(*x));
    x->path = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) { x->path[i] = path[i]; }
    x->n = n;
    x->next = NULL;
    return x;
}

typedef struct PathListStrcut {
    PLNode head;
    int count;
}*PathList;

PathList PathListCreate() {
    PathList pl = (PathList)malloc(sizeof(*pl));
    pl->head = NULL;
    pl->count = 0;
    return pl;
}

void PathListAdd(PathList pl, int *path, int n) {
    PLNode head = PLNodeCreate(path, n);
    head->next = pl->head;
    pl->head = head;
    pl->count++;
}

int* PathListDelete(PathList pl, int *n) {
    PLNode head = pl->head;
    pl->head = head->next;
    pl->count--;
    int *path = head->path;
    *n = head->n;
    free(head);
    return path;
}

int PathListCount(PathList pl) { return pl->count; }

bool PathListIsEmpty(PathList pl) { return pl->count == 0; }

char** create_transformation_sequence(int *path, int n, char *beginWord, char **wordList) {
    char **ts = (char**)malloc(n * sizeof(*ts));
    ts[0] = beginWord;
    for (int i = 1; i < n; i++) { ts[i] = wordList[path[i] - 1]; }
    return ts;
}

int* calculate_edge_to(int **table, int n, int *tableSize, int source, int qsize) {
    int *edgeTo = (int*)malloc(n * sizeof(*edgeTo));
    bool *marked = (bool*)malloc(n * sizeof(*marked));
    for (int i = 0; i < n; i++) { marked[i] = false; }
    marked[source] = true;
    Queue queue = QueueCreate(qsize);
    QueueEnqueue(queue, source);
    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));
    return edgeTo;
}

int shortest_path_length(int **table, int n, int *tableSize, int source, int target, int qsize, int *edgeTo) {
    int min = 0;
    for (int v = target; v != source; v = edgeTo[v]) { 
        if (v >= 0 && v < n) {
            min++; 
        } else {
            min = INT_MAX;
            break;
        }
    }
    
    return min == INT_MAX ? INT_MAX : min + 1;
}

/*
* We do three prunings here:
* 1) leave out the vertices that should not be taken(see footnote for
*    more info on the taken array here);
* 2) leave out the vertices that are already on the path(added previously
*    along the way of the dfs);
* 3) leave out the vertiecs that are NOT one step further torward the dst
*    vertex(the vertex corresponding to endWord).
* footnote: we take into consideration only such vertices that the 
*           sum of the distance from the source(the vertex 
*           corresponding to beginWord) and the distance to the 
*           destination vertex(the vertex corresponding to endWord)
*           equals the pre-calculated length of the shortest path.
*/
void dfs(int **table, int n, int *tableSize, bool *taken, int *dstToSrc, int v, int target, int spl/*shortest path length*/, int *path, int pi/*path index*/, bool *opf/*on path flags*/, PathList pathList) {
    if (!taken[v]) return;
    int *adj = table[v];
    for (int i = 0; i < tableSize[v]; i++) {
        int w = adj[i];
        if (!opf[w] && (dstToSrc[w] == dstToSrc[v] + 1)) {
            if (pi < spl) {
                path[pi] = w;
                opf[w] = true;
                if (w == target) { 
                    PathListAdd(pathList, path, spl);
                    opf[w] = false;
                } else {
                    if (pi + 1 < spl) { dfs(table, n, tableSize, taken, dstToSrc, w, target, spl, path, pi + 1, opf, pathList); }
                    opf[w] = false;
                }
            } else {
                break;
            }
        }
    }
}

/**
* checks if word differs from key by one&only one character
*/
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;
}

char *** findLadders(char * beginWord, char * endWord, char ** wordList, int wordListSize, int* returnSize, int** returnColumnSizes) {
    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) { 
        *returnSize = 0;
        return NULL;
    }

    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 *edgeToSrc = calculate_edge_to(table, wordListSize + 1, tableSize, 0, qsize);
    int min = shortest_path_length(table, wordListSize + 1, tableSize, 0, target, qsize, edgeToSrc);
    if (min == INT_MAX) {//not reachable from beginWord
        *returnSize = 0;
        return NULL;
    }
    int *edgeToDst = calculate_edge_to(table, wordListSize + 1, tableSize, target, qsize);
    bool *taken = (bool*)malloc(sizeof(*taken) * (wordListSize + 1));
    int *dstToSrc = (int*)malloc((wordListSize +1) * sizeof(*dstToSrc));
    for (int v = 0; v <= wordListSize; v++) { 
        int ls = shortest_path_length(table, wordListSize + 1, tableSize, 0, v, qsize, edgeToSrc);
        int ld = shortest_path_length(table, wordListSize + 1, tableSize, target, v, qsize, edgeToDst);
        if (ls == INT_MAX) { ls = 0; }
        if (ld == INT_MAX) { ld = 0; }
        taken[v] = (min + 1) == (ls + ld);
        dstToSrc[v] = ls;
    }

    bool *opf = (bool*)malloc((wordListSize + 1) * sizeof(*opf));
    opf[0] = true;
    for (int i = 1; i <= wordListSize; i++) { opf[i] = false; }
    PathList pathList = PathListCreate();
    int *path = (int*)malloc(min * sizeof(*path));
    path[0] = 0;
    dfs(table, wordListSize + 1, tableSize, taken, dstToSrc, 0, target, min, path, 1, opf, pathList);
    *returnSize = PathListCount(pathList);
    *returnColumnSizes = (int*)malloc(*returnSize * sizeof(int));
    for (int i = 0; i < *returnSize; i++) { (*returnColumnSizes)[i] = min; }
    char ***switches = (char***)malloc(PathListCount(pathList) * sizeof(*switches));
    int i = 0;
    while (!PathListIsEmpty(pathList)) {
        int n = 0;
        int *path = PathListDelete(pathList, &n);
        switches[i] = create_transformation_sequence(path, n, beginWord, wordList);
        i++;
    }
    return switches;
}