522. 最長特殊序列 II#
文字列リスト strs が与えられた場合、最長の特殊な部分列 の長さを返します。最長の特殊な部分列が存在しない場合は、-1 を返します。
特殊な部分列 は次のように定義されます：その部分列は、ある文字列に 独自の部分列（他の文字列の部分列ではない） です。
s の 部分列 は、文字列 s の一部の文字を削除することで得られます。
-
例えば、
"abc"は"aebdc"の部分列です。アンダースコア文字を削除して"abc"を得ることができます。"aebdc"の部分列には、"aebdc"、"aeb"、""（空文字列）も含まれます。
例 1：
入力: strs = ["aba","cdc","eae"]
出力: 3
例 2:
入力: strs = ["aaa","aaa","aa"]
出力: -1
ヒント:
2 <= strs.length <= 501 <= strs[i].length <= 10strs[i]は小文字の英字のみを含みます
列挙#
strs = [ "abc", "abcd", "abcde" ] の場合、"abcd" は "abc" の部分列ではありませんが、"abcd" は abcde の部分列です。"abcde" は "abcd" や abc の部分列ではないため、求める最長の特殊な部分列は "abcde" です。
コードの実装：
class Solution {
public:
int findLUSlength(vector<string>& strs) {
// str1 が 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;
// 現在の文字列の長さが最長の特殊な部分列の長さよりも大きい場合にのみ、最長の特殊な部分列の長さが増加する可能性がある
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;
}
};
この問題は実際には難しくありませんが、間違いやすいです。上記のコードにはバグがあります。
バグは、現在の長さの判定が最長の特殊な部分列の長さよりも大きいかどうかの部分にあります if (strs[i].size() > res)。size() の戻り値の型は size_t であり、符号なしの型ですが、res は符号付きの型です。比較時に res は整数拡張が行われ、res は符号付きから符号なしに暗黙的に変換されます。64 ビットのオペレーティングシステム上では、res の値は になります。この暗黙的な変換の他にも、複数の場所で暗黙的な変換の問題があります。