主題
題目連結(jié)：
題目意譯：
你被給定一個(gè)字串陣列 words 以及一個(gè)陣列 groups。兩者長(zhǎng)度皆為 n。
兩個(gè)長(zhǎng)度相同的字串之「漢明距離」定義為相同位置的字元有多少組不同。
你需要從一個(gè)索引值陣列 [0, 1, ……, n - 1] 中選出一個(gè)最長(zhǎng)的子序列，使得對(duì)於一個(gè)長(zhǎng)度 k 的子序列（以 [i0, i1, ……, ik-1] 表示）來(lái)說(shuō)，以下為真：
對(duì)於子序列中相鄰的索引值，它們?cè)?groups 對(duì)應(yīng)元素彼此不同。即對(duì)於每一個(gè) 0 < j + 1 < k 的 j 值， groups[ij] != groups[ij+1]。
對(duì)於每一個(gè) 0 < j + 1 < k 的 j 值，words[ij] 和 words[ij+1] 的長(zhǎng)度相同，且兩者的漢明距離為 1。
回傳一個(gè)字串陣列包含著選定的子序列所對(duì)應(yīng)的字串（按照順序）。如果有多個(gè)答案存在，則回傳任意一個(gè)。
注：words 中的字串可能長(zhǎng)度不一。
限制：
1 ≦ n == words.length == groups.length ≦ 1000
1 ≦ words[i].length ≦ 10
1 ≦ groups[i] ≦ n
words 由相異字串組成。
words[i] 只由小寫英文字母組成。
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： words = ["bab","dab","cab"], groups = [1,2,2]
輸出： ["bab","cab"]
解釋： 一個(gè)可以被選出的子序列為 [0,2]。
groups[0] != groups[2]
words[0].length == words[2].length，且兩者之間的漢明距離為 1。
所以一個(gè)合法的答案為 [words[0],words[2]] = ["bab","cab"]。
Another subsequence that can be selected is [0,1].
groups[0] != groups[1]
words[0].length == words[1].length，且兩者之間的漢明距離為 1。
所以另一個(gè)合法的答案為 [words[0],words[1]] = ["bab","dab"]。
可以證明滿足條件的最長(zhǎng)索引值子序列之長(zhǎng)度為 2。
範(fàn)例 2：
輸入： words = ["a","b","c","d"], groups = [1,2,3,4]
輸出： ["a","b","c","d"]
解釋： 我們可以被選出子序列 [0,1,2,3]。
其滿足兩個(gè)所需條件。
因此答案為 [words[0],words[1],words[2],words[3]] = ["a","b","c","d"]。
其長(zhǎng)度是所有滿足條件的子序列最長(zhǎng)的。
因此其為唯一解。
解題思維：
首先，長(zhǎng)度相同的字串才有可能被選在一起。因此先掃過一次 words（以及 groups，因?yàn)閮烧呤且惑w同心的），然後把相同長(zhǎng)度的字串放到同一組（可以用陣列等任意資料結(jié)構(gòu)存）。因此此時(shí)的所求為每一組中取最長(zhǎng)者之後再?gòu)倪@些取最長(zhǎng)者出來(lái)。
對(duì)於同一組的字串來(lái)說(shuō)，昨天的策略不能再用了。因?yàn)楝F(xiàn)在 groups 中的數(shù)字不是只有兩種而已，因此每一種數(shù)字的後面不是只能接唯一一種數(shù)字，而是可能會(huì)有好幾種。不過此時(shí)按照類似這題的方式用動(dòng)態(tài)規(guī)劃（Dynamic Programming）求解（連遞迴式都長(zhǎng)得差不多，只是現(xiàn)在只要數(shù)字不一樣就可以接）即可。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
