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:

Input: "aba", "cdc", "eae"
Output: 3

Note:

1. All the given strings’ lengths will not exceed 10.
2. The length of the given list will be in the range of [2, 50].

---

给定一个字符串数组，问这些字符串的最长非公共子序列的长度是多少。非公共子序列是指任意一个字符串的子序列，不是其他所有字符串的子序列。要求这样的子序列的最大长度。 首先非公共子序列不可能来自那些出现过多次的字符串，比如数组中有两个字符串都是”abcd”，那么其中一个”abcd”的任意一个子序列，必定是另一个”abcd”的子序列，不满足非公共子序列的定义。所以我们首先对所有字符串及其出现频率hash一下，只考察那些出现一次的字符串的子序列。 另一个观察是，如果存在非公共子序列，则最长的非公共子序列肯定是某个完整的字符串，这一点从LeetCode Longest Uncommon Subsequence I可知。 所以，我们首先把字符串按长度从大到小排序，排序完之后，遍历每个字符串s，如果s出现的频率大于1，直接不考虑；否则，采用贪心策略，我们在比s更长的那些字符串中判断s是否是他们的子序列，如果是，s不是非公共子序列；否则s是非公共子序列，因为后面都是比s更短的字符串，s肯定也不是他们的子序列，又我们根据字符串长度排序了。所以s的长度就是非公共子序列的最大长度。 完整代码如下： [cpp] class Solution { private: // 判断child是否是par的子序列 bool isSubSeq(const string& par, const string& child) { int i = 0, j = 0, m = par.size(), n = child.size(); while (i < m&&j < n) { if (par[i] == child[j])++j; ++i; } return j == n; } public: int findLUSlength(vector<string>& strs) { unordered_map<string, int> hash; for (const auto& s : strs)++hash[s]; sort(strs.begin(), strs.end(), [](const string& s1, const string& s2) {return s1.size() > s2.size(); }); for (int i = 0; i < strs.size(); ++i) { if (hash[strs[i]] > 1)continue; bool isSub = false; for (int j = i – 1; j >= 0; –j) { if (isSubSeq(strs[j], strs[i])) { isSub = true; break; } } if (!isSub)return strs[i].size(); } return -1; } }; [/cpp] 本代码提交AC，用时3MS。 参考：http://bookshadow.com/weblog/2017/04/03/leetcode-longest-uncommon-subsequence-ii/]]>