Computer >> Máy Tính >  >> Lập trình >> C ++

Chuỗi chuỗi dài nhất trong C ++

Giả sử chúng ta có một danh sách các từ, ở đây mỗi từ bao gồm các chữ cái viết thường. Vì vậy, một từ word1 là tiền thân của một từ khác word2 nếu và chỉ khi chúng ta có thể thêm chính xác một chữ cái vào bất kỳ đâu trong word1 để làm cho nó bằng với word2. Đối với ví dụ của tiền thân là như thế, "abc" là một tiền thân của "bàn tính". Giờ đây, một chuỗi từ là một chuỗi các từ [từ_1, từ_2, ..., từ_k] với k> =1, trong đó từ_1 là tiền nhiệm của từ_2, từ_2 là từ trước của từ_3, v.v. Chúng ta phải tìm độ dài dài nhất có thể của một chuỗi từ với các từ được chọn từ danh sách các từ đã cho.

Vì vậy, nếu đầu vào là:["a", "b", "ba", "bca", "bda", "bdca"], thì kết quả sẽ là 4, vì một trong những chuỗi dài nhất sẽ là [“ a ”,“ ba ”,“ bda ”,“ bdca ”].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định bản đồ dp, n:=kích thước của mảng từ

  • sắp xếp mảng từ dựa trên độ dài

  • ret:=0

  • đối với tôi trong phạm vi 0 tn n - 1

    • tốt nhất:=0

    • cho j trong phạm vi từ 0 đến độ dài của từ [i] - 1

      • word:=(chuỗi con của các từ [i] từ 0 đến j - 1) nối (chuỗi con của các từ [i] từ j + 1 đến cuối)

      • tốt nhất:=max of best, dp [word] + 1

    • dp [words [i]]:=best

    • ret:=max of (ret, dp [words [i]])

  • trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

#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));
}

Đầu vào 

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

Đầu ra 

4