題目連結:
題目意譯:
給定一字串陣列 strs,回傳它們之間的最長相異子序列之長度。如果最長相異子字串不存在,則回傳 -1。
一字串陣列中的一個相異子序列是一個字串其滿足為其中一個字串的子序列,但不是其他字串的子序列。
一字串 s 的一個子序列為可以藉由刪除 s 中任意數量的字元而得到的字串。
例如,"abc" 為 "aebdc" 的一個子序列因為你可以刪除 "aebdc" 中劃底線的部分而得到 "abc"。"aebdc" 的其他子序列還包括 "aebdc" 、 "aeb" 和 ""(空字串)。
限制:
1 ≦ strs.length ≦ 50
1 ≦ strs[i].length ≦ 10
strs[i] 由小寫英文字母組成。
範例測資:
範例 1:
輸入: strs = ["aba","cdc","eae"]
輸出: 3
範例 2:
輸入: strs = ["aaa","aaa","aa"]
輸出: -1
解題思維:
從
這題可以推論出:存在一字串 s 其是以 strs[i] 為準(也就是 s 是 strs[i] 的子序列,但不是其他字串的)的相異子序列,若且唯若 strs[i] 本身也是一個相異子序列。
因此對於以 strs[i] 為準的最長相異子序列,只需要檢查 strs[i] 本身是不是相異子序列即可。如果是 strs[i] 就是 strs[i] 的最長相異子序列。
所以我們可以掃過所有 strs 中的字串 strs[i],並以它為準去檢查其他字串是否含有 strs[i] 作為子序列存在。而這個檢查可以參見
這題的作法。
掃完後,裡面最長的相異子序列(也就是最長的、是相異子序列的 strs[i])即是所求;如果所有字串都不是相異子序列,則回傳 -1。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。