522. Longest Uncommon Subsequence II#
Given a list of strings strs, return the length of the longest uncommon subsequence. If the longest uncommon subsequence does not exist, return -1.
A subsequence of a string s can be obtained by deleting some characters from s.
A special subsequence is a subsequence that is unique and cannot be a subsequence of any other string.
For example, "abc" is a subsequence of "aebdc", as you can delete the underscore characters in "aebdc" to obtain "abc". The subsequence of "aebdc" also includes "aebdc", "aeb", and "" (empty string).
Example 1:
Input: strs = ["aba","cdc","eae"]
Output: 3
Example 2:
Input: strs = ["aaa","aaa","aa"]
Output: -1
Constraints:
2 <= strs.length <= 501 <= strs[i].length <= 10strs[i]consists of lowercase English letters
Enumeration#
If strs = ["abc", "abcd", "abcde"], "abcd" is not a subsequence of "abc", but "abcd" is a subsequence of "abcde", and "abcde" is not a subsequence of "abcd" or "abc". Therefore, the longest uncommon subsequence we are looking for is "abcde".
Here is the implementation:
class Solution {
public:
int findLUSlength(vector<string>& strs) {
// Check if str1 is a subsequence of str2
auto isSub = [&](const string &str1, const string &str2) -> bool {
int j = 0;
for (int i = 0; i < str2.size(); ++i) {
if (str1[j] == str2[i]) {
++j;
}
}
return j == str1.size();
};
int res = -1;
for (int i = 0; i < strs.size(); ++i) {
bool flag = true;
// Only consider the length of the current string if it is greater than the length of the longest uncommon subsequence
if (strs[i].size() > res) {
for (int j = 0; j < strs.size(); ++j) {
if (j != i && isSub(strs[i], strs[j])) {
flag = false;
break;
}
}
if (flag) {
res = strs[i].size();
}
}
}
return res;
}
};
This problem is actually not difficult, but it is easy to make mistakes. The above code actually has a bug.
The bug lies in the comparison of the length of the current string with the length of the longest uncommon subsequence if (strs[i].size() > res). The size() function returns a size_t type, which is an unsigned type, while res is a signed type. When comparing them, res is implicitly promoted to an unsigned type, and on a 64-bit operating system, the value of res becomes . In addition to this implicit conversion, there are multiple implicit conversion issues in the code.