A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
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.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
Constraints:
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters.
beginWord != endWord
All the words in wordList are unique.
xianyu
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAX_WORD_LENGTH 11 // 定義單詞的最大長度為 11
// 判斷兩個單詞是否只差一個字元
bool isOneLetterDiff(char* word1, char* word2) {
int diffCount = 0; // 用於計算不同字元的數量
// 遍歷單字的每個字元
for (int i = 0; word1[i] != '\0'; i++) {
// 如果字元不同，增加count
if (word1[i] != word2[i]) {
diffCount++;
}
// 如果不同字元超過 1 個，返回 false
if (diffCount > 1) {
return false;
}
}
// 如果正好只差一個字元，返回 true
return diffCount == 1;
}
// BFS 主函數
int ladderLength(char* beginWord, char* endWord, char** wordList, int wordListSize) {
// 檢查 endWord 是否存在於 wordList 中
bool endWordInList = false; // 記錄 endWord 是否在 wordList 中
for (int i = 0; i < wordListSize; i++) {
// 如果找到了 endWord，設置標記為 true
if (strcmp(wordList[i], endWord) == 0) {
endWordInList = true;
break;
}
}
// 如果 endWord 不在 wordList 中，return 0
if (!endWordInList) return 0;
// 建立一個訪問標記陣列，記錄 wordList 中的單詞是否已經被visit過
bool* visited = (bool*)calloc(wordListSize, sizeof(bool));
// 創建佇列，用於 BFS 存儲單詞
char** queue = (char**)malloc(wordListSize * sizeof(char*));
// 創建步數陣列，用於記錄到達每個單詞的步數
int* steps = (int*)malloc(wordListSize * sizeof(int));
int front = 0, rear = 0; // 初始化佇列的頭尾pointer
// 初始化佇列，將 beginWord 放入佇列中，步數設為 1
queue[rear] = beginWord;
steps[rear] = 1;
rear++; // 佇列尾pointer後移
// BFS 遍歷
while (front < rear) {
char* currentWord = queue[front]; // 取出佇列頭部的單詞
int currentStep = steps[front]; // 取出當前步數
front++; // 佇列front pointer後移
// 遍歷 wordList 中的每個單詞
for (int i = 0; i < wordListSize; i++) {
// 如果該單詞未被訪問過且與當前單詞只差一個字元
if (!visited[i] && isOneLetterDiff(currentWord, wordList[i])) {
// 如果找到了 endWord，返回當前步數加 1
if (strcmp(wordList[i], endWord) == 0) {
free(visited); // 釋放訪問標記數組的記憶體
free(queue); // 釋放佇列的記憶體
free(steps); // 釋放步數數組的記憶體
return currentStep + 1; // 返回結果
}
// 如果不是 endWord，將新單詞加入佇列
queue[rear] = wordList[i];
steps[rear] = currentStep + 1; // 記錄步數加 1
visited[i] = true; // 標記該單詞已被訪問
rear++; // 佇列尾指針後移
}
}
}
// 如果 BFS 結束未找到 endWord，釋放memory
free(visited);
free(queue);
free(steps);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAX_WORD_LENGTH 11 // 定義單詞的最大長度為 11
// 判斷兩個單詞是否只差一個字元
bool isOneLetterDiff(char* word1, char* word2) {
int diffCount = 0; // 用於計算不同字元的數量
// 遍歷單字的每個字元
for (int i = 0; word1[i] != '\0'; i++) {
// 如果字元不同，增加count
if (word1[i] != word2[i]) {
diffCount++;
}
// 如果不同字元超過 1 個，返回 false
if (diffCount > 1) {
return false;
}
}
// 如果正好只差一個字元，返回 true
return diffCount == 1;
}
// BFS 主函數
int ladderLength(char* beginWord, char* endWord, char** wordList, int wordListSize) {
// 檢查 endWord 是否存在於 wordList 中
bool endWordInList = false; // 記錄 endWord 是否在 wordList 中
for (int i = 0; i < wordListSize; i++) {
// 如果找到了 endWord，設置標記為 true
if (strcmp(wordList[i], endWord) == 0) {
endWordInList = true;
break;
}
}
// 如果 endWord 不在 wordList 中，return 0
if (!endWordInList) return 0;
// 建立一個訪問標記陣列，記錄 wordList 中的單詞是否已經被visit過
bool* visited = (bool*)calloc(wordListSize, sizeof(bool));
// 創建佇列，用於 BFS 存儲單詞
char** queue = (char**)malloc(wordListSize * sizeof(char*));
// 創建步數陣列，用於記錄到達每個單詞的步數
int* steps = (int*)malloc(wordListSize * sizeof(int));
int front = 0, rear = 0; // 初始化佇列的頭尾pointer
// 初始化佇列，將 beginWord 放入佇列中，步數設為 1
queue[rear] = beginWord;
steps[rear] = 1;
rear++; // 佇列尾pointer後移
// BFS 遍歷
while (front < rear) {
char* currentWord = queue[front]; // 取出佇列頭部的單詞
int currentStep = steps[front]; // 取出當前步數
front++; // 佇列front pointer後移
// 遍歷 wordList 中的每個單詞
for (int i = 0; i < wordListSize; i++) {
// 如果該單詞未被訪問過且與當前單詞只差一個字元
if (!visited[i] && isOneLetterDiff(currentWord, wordList[i])) {
// 如果找到了 endWord，返回當前步數加 1
if (strcmp(wordList[i], endWord) == 0) {
free(visited); // 釋放訪問標記數組的記憶體
free(queue); // 釋放佇列的記憶體
free(steps); // 釋放步數數組的記憶體
return currentStep + 1; // 返回結果
}
// 如果不是 endWord，將新單詞加入佇列
queue[rear] = wordList[i];
steps[rear] = currentStep + 1; // 記錄步數加 1
visited[i] = true; // 標記該單詞已被訪問
rear++; // 佇列尾指針後移
}
}
}
// 如果 BFS 結束未找到 endWord，釋放memory
free(visited);
free(queue);
free(steps);
return 0;
}
// 測試函數
void testLadderLength() {
// 測試範例 1
char* wordList1[] = {"hot", "dot", "dog", "lot", "log", "cog"};
int wordListSize1 = 6; // wordList1 的大小
printf("Test case 1: %d\n", ladderLength("hit", "cog", wordList1, wordListSize1)); // 輸出應為 5
// 測試範例 2
char* wordList2[] = {"hot", "dot", "dog", "lot", "log"};
int wordListSize2 = 5; // wordList2 的大小
printf("Test case 2: %d\n", ladderLength("hit", "cog", wordList2, wordListSize2)); // 輸出應為 0
}
// 主測試函數
int main() {
testLadderLength();
return 0;
}
iThome鐵人賽
看影片追技術