前往
大廳
主題

LeetCode - 521. Longest Uncommon Subsequence I 解題心得

Not In My Back Yard | 2020-11-11 00:00:01 | 巴幣 10 | 人氣 427

題目連結:


題目意譯:
給定兩字串 a 和 b,找到兩者的最長相異子序列之長度。

一個字串 s 的子序列為一字串其可由 s 刪除任意數量的字元而來。例如,字串 "abc" 是字串 "aebdc" 的一個子序列,因為你可以藉由從 "aebdc" 刪掉「e」和「d」得到 "abc"。 其他為 "aebdc" 的子序列包含 "aebdc" 、 "aeb" 以及 ""(空字串)。

兩字串的一個相異子序列是一個字串其滿足為其中一個字串的子序列,而不是另一個字串的子序列。

回傳 a 和 b 的最長相異子序列之長度。如果最長相異子序列不存在,則回傳 -1 。

限制:
1 ≦ a.length, b.length ≦ 100
a 和 b 只由小寫英文字母組成。



範例測資:
範例 1:
輸入: a = "aba" , b = "cdc"
輸出: 3
解釋: 其中一個最長相異子序列為 "aba",因為 "aba" 是 "aba" 的一個子序列但不是 "cdc" 的。注意,"cdc" 也為一個最長相異子序列。

範例 2:
輸入: a = "aaa" , b = "bbb"
輸出: 3
解釋: 最長相異子序列為 "aaa" 和 "bbb"。

範例 3:
輸入: a = "aaa" , b = "aaa"
輸出: -1
解釋: 每個 a 的子序列都正好是 b 的子序列。相似地,每個 b 的子序列也恰好為 a 的一個子序列。


解題思維:
可以看到當字串 a 或字串 b 為空字串,或是字串 a 與字串 b 完全相同時,並不存在任何的相異子序列。因此,輸出 -1 。

而其他的情況,看字串 a 與字串 b 何者長度較長,該長度即為所求(因為 a ≠ b,所以兩者都是相異子序列)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作