最長的字符串

Question

所以我最近在接受採訪時這樣一個問題：

鑑於字典和起始字符串，什麼是可以形成由最長的單詞每次在輸入字符串的前面和後面添加一個字符，每個新單詞都必須出現在字典中？

例如：輸入= '在' 字典= {帽子，聊天，大鼠，TAT，紋身，chatats}

返回 '聊天'，這是因爲：在 - >帽 - >聊天 - >聊天

我想到了一個解決方案，我們蠻力並嘗試從輸入字符串的前面和後面添加所有字母 - 如果新字符串存在，然後我們暴露前面和後面的26個字母，最終得到最終字符串。

我想知道是否有一個更有效的方法來解決這個問題，而不是強迫所有26個字母前後每次都蠻力？

我想到的一種方法是通過字典，如果輸入字符串作爲子字符串存在於任何長度大於改變輸入字符串長度的條目，那麼從輸入字符串中刪除輸入子字符串。

例：第一次迭代之後，字典是= {H，聊天，R，T，紋身，chatats}

而且我們也必須爲每個條目的長度可變的保持原始長度的軌道的條目。但我不確定這是否是一種正確的方法/甚至是可行的。

Answer 1

構建單詞及其較短/較長版本的圖形，例如在問題（hat, chat, chats, rat, tat, tats, chatats）字列表中，這將是：

      chatats 
hat ─── chat ─── chats 
rat 
tat ─── tats 

構建圖形向後，即對於每一個字，通過除去任一前導或尾隨字符查找2個較短的話。

爲了更快速地查找，請爲他們的圖形節點創建一個Map的單詞。

現在找到圖中最長的鏈。