banner
cells

cells

为美好的世界献上 bug

522. Longest Subsequence II

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 <= 50
  • 1 <= strs[i].length <= 10
  • strs[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 264+12^{64}+1. In addition to this implicit conversion, there are multiple implicit conversion issues in the code.

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.