ห่วงโซ่สตริงที่ยาวที่สุดใน C ++

สมมติว่าเรามีรายการคำ ที่นี่แต่ละคำประกอบด้วยตัวพิมพ์เล็ก ดังนั้นหนึ่งคำ word1 จึงเป็นบรรพบุรุษของคำอื่น word2 ถ้าหากเราสามารถเพิ่มตัวอักษรหนึ่งตัวที่ใดก็ได้ใน word1 เพื่อให้เท่ากับ word2 สำหรับตัวอย่างของรุ่นก่อนเช่น "abc" ก็คือบรรพบุรุษของ "abac" ตอนนี้ ห่วงโซ่คำคือลำดับของคำ [word_1, word_2, ..., word_k] ที่มี k>=1 โดยที่ word_1 เป็นผู้บุกเบิกของ word_2, word_2 มาก่อน word_3 เป็นต้น เราต้องหาความยาวของชุดคำที่ยาวที่สุดด้วยคำที่เลือกจากรายการคำที่กำหนด

ดังนั้นหากอินพุตเป็นเช่น:["a","b","ba","bca","bda","bdca"] ผลลัพธ์จะเป็น 4 เนื่องจากหนึ่งในสายที่ยาวที่สุดจะเป็น [“ a”, “ba”, “bda”, “bdca”].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดแผนที่ dp, n :=ขนาดของอาร์เรย์คำ

• เรียงคำตามความยาว

• ยกเลิก :=0

• สำหรับฉันในช่วง 0 tn n – 1

  • ดีที่สุด :=0

  • สำหรับ j ในช่วง 0 ถึงความยาวของคำ[i] – 1

    • word :=(สตริงย่อยของคำ[i] จาก 0 ถึง j – 1) ต่อกัน (สตริงย่อยของคำ[i] จาก j + 1 ถึงตอนจบ)

    • ดีที่สุด :=สูงสุดของดีที่สุด dp[word] + 1

  • dp[words[i]] :=ดีที่สุด

  • ret :=สูงสุดของ (ret, dp[words[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"]

ผลลัพธ์

4