主題
題目連結(jié)：
題目意譯：
一個(gè)基因字串可以被一個(gè) 8 字元長(zhǎng)的字串所表示，其字元之選擇為 'A' 、 'C' 、 'G' 或 'T'。
假設(shè)我們需要進(jìn)行從一個(gè)基因字串 start 突變到另一個(gè)基因字串 end 的調(diào)查，其中一次突變定義為在基因字串中單一一個(gè)字元之變化。
例如，"AACCGGTT" --> "AACCGGTA" 是一次的突變。
現(xiàn)在同時(shí)有一個(gè)基因銀行 bank，其將記錄著所有可行的基因突變。一個(gè)基因必須存在於銀行中才是合法的基因字串。
給定兩個(gè)基因字串 start 和 end 以及基因銀行 bank，回傳從 start 突變到 end 的最少所需步數(shù)。因?yàn)椴淮嬖谶@樣子的突變序列，回傳 -1。
注意一開始字串被「假設(shè)」為合法的字串，因此其有可能不會(huì)包含於 bank 之中。
限制：
start.length == 8
end.length == 8
0 ≦ bank.length ≦ 10
bank[i].length == 8
start 、 end 和 bank[i] 只由字元 ['A', 'C', 'G', 'T'] 組成。
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
輸出： 1
範(fàn)例 2：
輸入： start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
輸出： 2
範(fàn)例 3：
輸入： start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
輸出： 3
解題思維：
就是單純地從 start 這個(gè)字串開始廣度優(yōu)先搜尋（Breadth First Search，BFS），即先算出 start 可以生出 bank 中哪些字串。窮舉每種變化即可。雖然每個(gè)字元只有 4 種選擇，使得可能性最多會(huì)有 4 ^ 8 個(gè)。但是 bank 的長(zhǎng)度最大是 10，所以最多只會(huì)生出 10 個(gè)。
然後從第一步生出來的字串再疊代一次，形成第二步的那些字串（忽略已經(jīng)出現(xiàn)過的，包含 start）。而期間如果遇到 end 這個(gè)字串，即代表當(dāng)前步數(shù)即是所求最少步數(shù)；而如果 bank 中能被產(chǎn)生出來的字串都出來後也沒有 end 這個(gè)字串，則回傳 -1。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
