C++에서 가장 긴 Uncommon Subsequence II

<시간/>

문자열 목록이 있다고 가정합니다. 우리는 그들 중에서 가장 길고 드문 부분 수열을 찾아야 합니다. 가장 길고 흔하지 않은 하위 시퀀스는 실제로 이러한 문자열 중 하나의 가장 긴 하위 시퀀스이며 이 하위 시퀀스는 다른 문자열의 하위 시퀀스가 아니어야 합니다.

하위 시퀀스는 나머지 요소의 순서를 변경하지 않고 일부 문자를 삭제하여 하나의 시퀀스에서 파생될 수 있는 시퀀스라는 것을 알고 있습니다.

여기서 우리는 문자열 목록을 가져오고 출력은 가장 길고 드문 부분 시퀀스의 길이여야 합니다. 가장 긴 uncommon 하위 시퀀스가 없으면 -1을 반환합니다.

따라서 입력이 "aba", "cdc", "eae"와 같으면 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

isSubsequence() 함수를 정의하면, b,
j :=0
initialize i :=0의 경우, i
- j
  - (j를 1씩 증가)
b의 크기가 j와 같을 때 true를 반환
getDuplicates() 함수를 정의하면 배열 strs가 필요합니다.
한 세트 방문 및 다른 세트 ret 정의
for initialize i :=0, i
- strs[i]가 방문한 경우 -
  - strs[i]를 ret에 삽입
- 방문
  에 strs[i] 삽입
리턴 렛
기본 방법에서 다음을 수행하십시오 -
문자열 길이에 따라 배열 strs 정렬
하나의 세트 중복 정의 :=getDuplicates(strs)
for initialize i :=0, i
- strs[i]가 중복된 경우 -
  - 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
- i가 0과 같으면 -
  - strs[i]
    의 크기를 반환
- j:=0 초기화의 경우, j
  - isSubsequence(strs[j], strs[i])가 거짓이면 -
    - j가 i - 1과 같으면 -
      - strs[i]
        의 크기를 반환
  - 그렇지 않으면
    - 루프에서 나오세요
반환 -1

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   static bool cmp(string a, string b){
      return a.size() > b.size();
   }
   int findLUSlength(vector<string>& strs){
      sort(strs.begin(), strs.end(), cmp);
      set<string> duplicates = getDuplicates(strs);
      for (int i = 0; i < strs.size(); i++) {
         if (duplicates.count(strs[i]))
            continue;
         if (i == 0)
            return strs[i].size();
         for (int j = 0; j < i; j++) {
            if (!isSubsequence(strs[j], strs[i])) {
               if ((j == i - 1)) {
                  cout << i << endl;
                  return strs[i].size();
               }
            }
            else
            break;
         }
      }
      return -1;
   }
   bool isSubsequence(string a, string b){
      int j = 0;
      for (int i = 0; i < a.size(); i++) {
         if (j < b.size() && a[i] == b[j])
            j++;
      }
      return j == b.size();
   }
   set<string> getDuplicates(vector<string>& strs){
      set<string> visited;
      set<string> ret;
      for (int i = 0; i < strs.size(); i++) {
         if (visited.count(strs[i])) {
            ret.insert(strs[i]);
         }
         visited.insert(strs[i]);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"aba", "cdc", "eae"};
   cout << (ob.findLUSlength(v));
}

입력

{"aba", "cdc", "eae"}