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;
}
