tags: String, BFS
Given two words(beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time.
- Each intermediate word must exist in the word list.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
Function:
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
// Your Code
}
題目分析
該題目是一道基于String旁理、LeetCode Medium的題目亥鸠。顯然可以用BFS算法求解：以beginWord為起點硬耍，以beginWord的下一跳為目標廣度優(yōu)先搜索wordList饺饭，并將符合條件的結(jié)果放入新的結(jié)果集中，然后對其進行新一輪的廣度優(yōu)先搜索，最終看是否能達到endWord聊疲。
下面會看到3個解法，分別是自己失敗且丑陋的解法沪悲、常見的解法以及高效的解法获洲。
算法1：自己的解法
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
int result = 1;
Set<String> wordListCopy = new HashSet<>(); // wordList的Clone，不影響原數(shù)據(jù)集的內(nèi)容
wordListCopy.addAll(wordList);
wordListCopy.add(endWord);
ArrayList<String> curAL = new ArrayList<>(); // BFS的隊列
curAL.add(beginWord);
ArrayList<String> otherAL = new ArrayList<>(); // 存儲新加入的元素
Set<String> remove = new HashSet<>(); // 3.wordListCopy中應(yīng)該刪除的元素集合
while (!curAL.contains(endWord)) {
otherAL.clear();
for (String temp : curAL) {
for (String s : wordListCopy) { // 判斷集合剩余的元素與隊列元素是否相鄰
if (isNeighbor(temp, s)) { // 1.調(diào)用判斷neighbor方法殿如，TLE的關(guān)鍵
otherAL.add(s);
remove.add(s);
}
}
remove.forEach(wordListCopy::remove); // 2.將新獲取的元素在wordListCopy中刪除
remove.clear();
}
ArrayList<String> temp = curAL; // 4.我也不懂自己在做什么
curAL = otherAL;
otherAL = temp;
result++; // 計算距離
if (curAL.size() == 0)
return 0;
}
return result;
}
public boolean isNeighbor(String s1, String s2) {
int len = s1.length();
char[] ch1 = s1.toCharArray();
char[] ch2 = s2.toCharArray();
int diff = 0;
for (int i=0; i<len&&diff<2; i++) { // 逐個字符的判斷兩者的距離
if (ch1[i]!=ch2[i]) {
diff++;
}
}
return diff <= 1;
}
雖然是幾個月之前寫的算法贡珊，但看上去還是那么親切，真是熱淚盈眶握截，簡直丑爆了飞崖。根據(jù)嚴重程度烂叔，依次分析代碼為什么TLE谨胞，為什么寫得這么丑陋。
- 判斷相鄰字符串是String類型的常見問題蒜鸡，開始看到他人代碼中對字符串的每一個字符遍歷26個字母感到不解胯努，認為自己的
isNeighbor方法效率會更高，然而在嘗試將他人代碼的該模塊改成自己的isNeighbor時逢防，TLE叶沛。經(jīng)過仔細考慮，自己的想法太naive了：假設(shè)候選隊列中有k個字符串忘朝，wordList剩有c個字符串灰署，每個字符串的長度為l，字符遍歷的復(fù)雜度為k*l*26局嘁，而自己方法的復(fù)雜度為k*c*l溉箕。很顯然，后者比前者多了一個系數(shù)c悦昵，而且很可能c>>26肴茄，所以后者效率遠不及前者，造成TLE但指。 - 這一塊的代碼寫得很丑陋寡痰，原因是開始我嘗試在
foreach循環(huán)中直接刪除wordListCopy中被訪問到的元素，但會拋出Concurrent ModificationException的異常棋凳。在當時編寫代碼時并不知道如何解決這個問題拦坠，所以改寫的這么丑陋。最近復(fù)習(xí)Java集合的過程中找到了問題的根源：集合的迭代器在遍歷過程中不允許修改集合信息剩岳，否則會拋出上述異常贞滨。下面兩個算法都給出了相對優(yōu)雅的解決方案。 - remove集合其實和curAL保持實時一致卢肃，所以完全沒必要申請這樣一個集合做莫名其妙的記錄疲迂。
- 這個地方我也無力吐槽了才顿。。尤蒿。
算法2：常見的解法
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
Set<String> reached = new HashSet<>();
reached.add(beginWord);
wordList.add(endWord);
int distance = 1;
while(!reached.contains(endWord)) {
Set<String> toAdd = new HashSet<>();
for(String each : reached) {
for (int i = 0; i < each.length(); i++) {
char[] chars = each.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++) {
chars[i] = ch;
String word = new String(chars);
if(wordList.contains(word)) {
toAdd.add(word);
wordList.remove(word);
}
}
}
}
distance ++;
if(toAdd.size() == 0) return 0;
reached = toAdd;
}
return distance;
}
該解法是BFS算法的經(jīng)典實現(xiàn)郑气，簡單優(yōu)雅、略帶粗暴腰池。
- 簡單優(yōu)雅：算法中使用2個集合實現(xiàn)了當前隊列和候選隊列尾组，對相鄰字符串的求解使用字符遍歷的方法保證了效率，同時由于字符遍歷的方法不需要
wordList的迭代器示弓，因此可以在循環(huán)中調(diào)用remove方法讳侨。 - 略帶粗暴：調(diào)用
wordList的remove方法會對傳入?yún)?shù)的內(nèi)容產(chǎn)生修改，可能造成非預(yù)期的結(jié)果奏属。算法3提供了另一種"刪除元素的思路"跨跨。
算法3：高效的解法
public int wordLadder(String beginWord, String endWord, Set<String> wordList) {
Set<String> beginSet = new HashSet<>();
Set<String> endSet = new HashSet<>();
int len = 1;
HashSet<String> visited = new HashSet<>();
beginSet.add(beginWord);
endSet.add(endWord);
while (!beginSet.isEmpty() && !endSet.isEmpty()) {
if (beginSet.size() > endSet.size()) {
Set<String> set = beginSet;
beginSet = endSet;
endSet = set;
}
Set<String> temp = new HashSet<>();
for (String word : beginSet) {
char[] chs = word.toCharArray();
for (int i=0; i<chs.length; i++) {
for (char c='a'; c<='z'; c++) {
char old = chs[i];
chs[i] = c;
String target = String.valueOf(chs);
if (endSet.contains(target)) {
return len + 1;
}
if (!visited.contains(target) && wordList.contains(target)) {
temp.add(target);
visited.add(target);
}
chs[i] = old;
}
}
}
beginSet = temp;
len++;
}
return 0;
}
該解法的主要思想是從兩端進行廣度優(yōu)先搜索，也即維護兩個當前隊列囱皿，每次遍歷較小的隊列勇婴，查找是否在另一個隊列（找到路徑）、是否在剩余的wordList中（形成新的候選隊列）嘱腥。雖然我不知道這種思路的效率有沒有定理支持耕渴，但直觀的感受是算法2中的思想類似于單點的水波需要擴很大才能到達目標點橱脸，而算法3在起點和終點都產(chǎn)生水波，這樣可以擴較小的范圍就碰到彼此，也即找到一條可達路徑艾帐。假設(shè)wordList字符串的個數(shù)總共有n個，字符串的長度為l，則該算法的最壞情況就是遍歷所有的字符串仍沒有找到路徑今野，此時的時間復(fù)雜度為O(n*l)条霜，超過Java AC的90%。
總結(jié)
該題目難度不大旋圆，自己的實現(xiàn)卻讓人哭笑不得或南，需要從以下幾點加強自己的編碼訓(xùn)練：
- 字符串相關(guān)算法；
- 對常見算法——如BFS——的實現(xiàn)應(yīng)倒背如流；
- 努力編寫簡單優(yōu)雅的代碼。
