Word Transformation
Abridge problem statement
給你一個字典,請你將給定的字串 $A$ ,利用字典中的字,在最少次數下,轉換成字串 $B$。其中,轉換過程中,連續兩字串只能差一個字母,且長度需相同。
輸出最少次數為多少。
Solution sketch
利用 BFS。一定要記得,從queue中移除的點,不能再被加入queue中,不然會TLE
可以加速的一個方法,是先把可以轉換的連續兩字加上一條邊。之後在圖上做 BFS 會快很多,畢竟不用每次都做字串比對。