C语言 | Leetcode C语言题解之第433题最小基因变化

题目：

题解：

int minMutation(char * start, char * end, char ** bank, int bankSize) {int m = strlen(start);int **adj = (int **)malloc(sizeof(int *) * bankSize);int endIndex = -1;for (int i = 0; i < bankSize; i++) {adj[i] = (int *)malloc(sizeof(int) * bankSize);memset(adj[i], 0, sizeof(int) * bankSize);}for (int i = 0; i < bankSize; i++) {if (!strcmp(end, bank[i])) {endIndex = i;}for (int j = i + 1; j < bankSize; j++) {int mutations = 0;for (int k = 0; k < m; k++) {if (bank[i][k] != bank[j][k]) {mutations++;}if (mutations > 1) {break;}}if (mutations == 1) {adj[i][j] = 1;adj[j][i] = 1;}}}if (endIndex == -1) {return -1;}int *queue = (int *)malloc(sizeof(int) * bankSize);bool *visited = (bool *)malloc(sizeof(bool) * bankSize);memset(visited, 0, sizeof(bool) * bankSize);int head = 0;int tail = 0;int step = 1;for (int i = 0; i < bankSize; i++) {int mutations = 0;for (int k = 0; k < m; k++) {if (start[k] != bank[i][k]) {mutations++;}if (mutations > 1) {break;}}if (mutations == 1) {queue[tail++] = i;visited[i] = true;}}        while (head != tail) {int sz = tail - head;for (int i = 0; i < sz; i++) {int curr = queue[head++];if (curr == endIndex) {for (int i = 0; i < bankSize; i++) {free(adj[i]);}free(adj);free(queue);free(visited);return step;}for (int j = 0; j < bankSize; j++) {if (visited[j] || !adj[curr][j]) {continue;}visited[j] = true;queue[tail++] = j;}}step++;}for (int i = 0; i < bankSize; i++) {free(adj[i]);}free(adj);free(queue);free(visited);return -1; 
}