[LeetCode] Longest Uncommon Subsequence II 最長非共同子序列之二

Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.

A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.

The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1.

Example 1:

Note:

All the given strings' lengths will not exceed 10.

The length of the given list will be in the range of [2, 50].

解法一：

<a>class Solution {</a>

下面這種解法使用一些部落客能想到的優化手段，首先我們給字元串按長度來排序，将長度大的放到前面，這樣我們如果找到了非共同子序列，那麼直接傳回其長度即可，因為目前找到的肯定是最長的。然後我們用一個集合來記錄已經周遊過的字元串，利用集合的去重複特性，這樣在有大量的重複字元串的時候可以提高效率，然後我們開始周遊字元串，對于目前周遊到的字元串，我們和集合中的所有字元串相比，看其是否是某個的子序列，如果都不是，說明目前的就是最長的非共同子序列。注意如果目前的字元串是集合中某個字元串的子序列，那麼直接break出來，不用再和其他的比較了，這樣在集合中有大量的字元串時可以提高效率，最後别忘了将周遊過的字元串加入集合中，參見代碼如下：

解法二：

參考資料：

<a href="https://discuss.leetcode.com/topic/85033/checking-subsequence-without-hashing" target="_blank">https://discuss.leetcode.com/topic/85033/checking-subsequence-without-hashing</a>

，如需轉載請自行聯系原部落客。