C++에서 가장 긴 문자열 체인

<시간/>

단어 목록이 있다고 가정합니다. 여기에서 각 단어는 소문자로 구성됩니다. 따라서 한 단어 word1은 word2와 같게 만들기 위해 word1의 아무 곳에나 정확히 하나의 문자를 추가할 수 있는 경우에만 다른 단어 word2의 선행자입니다. 예를 들어 "abc"는 "abac"의 선행자입니다. 이제 단어 체인은 k>=1인 단어 [word_1, word_2, ..., word_k]의 시퀀스입니다. 여기서 word_1은 word_2의 선행 항목이고, word_2는 word_3의 선행 항목입니다. 주어진 단어 목록에서 선택한 단어를 사용하여 단어 체인의 가능한 가장 긴 길이를 찾아야 합니다.

따라서 입력이 ["a","b","ba","bca","bda","bdca"]와 같으면 가장 긴 체인 중 하나가 [" a", "ba", "bda", "bdca"].

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

맵 정의 dp, n :=단어 배열의 크기
길이에 따라 단어 배열 정렬
ret :=0
0 tn n – 1 범위의 i에 대해
- 최고 :=0
- 범위 0에서 단어[i] – 1의 길이까지의 j에 대해
  - word :=(단어[i]의 부분 문자열 0에서 j – 1) 연결(단어[i]의 부분 문자열 j + 1에서 끝까지)
  - 최고 :=최고의 최대값, dp[단어] + 1
- dp[단어[i]] :=최고
- ret :=최대 (ret, dp[단어[i]])
리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   static bool cmp(string s1, string s2){
      return s1.size() < s2.size();
   }
   int longestStrChain(vector<string>& words) {
      unordered_map <string, int> dp;
      int n = words.size();
      sort(words.begin(), words.end(), cmp);
      int ret = 0;
      for(int i = 0; i < n; i++){
         int best = 0;
         for(int j = 0; j < words[i].size(); j++){
            string word = words[i].substr(0, j) +
            words[i].substr(j + 1);
            best = max(best, dp[word] + 1);
         }
         dp[words[i]] = best;
         ret = max(ret, dp[words[i]]);
      }
      return ret;
   }
};
main(){
   vector<string> v = {"a","b","ba","bca","bda","bdca"};
   Solution ob;
   cout << (ob.longestStrChain(v));
}

입력

["a","b","ba","bca","bda","bdca"]

C++에서 가장 긴 문자열 체인

예

입력

출력