Dòng ký tự trong C ++

Giả sử chúng ta muốn triển khai lớp StreamChecker như sau -

• StreamChecker (words) - Đây là hàm tạo, khởi tạo cấu trúc dữ liệu với các từ đã cho.

• query (letter) - Giá trị này trả về true khi đối với một số k> =1, k ký tự cuối cùng được truy vấn (theo thứ tự từ cũ nhất đến mới nhất, bao gồm cả ký tự vừa được truy vấn này) đánh vần một trong các từ trong danh sách đã cho.

Vì vậy, nếu đầu vào giống như danh sách từ =["ce", "g", "lm"], thì hãy gọi truy vấn nhiều lần cho [a, b, c, e, f, g, h, i, j, k , l, m], thì đầu ra sẽ đúng với e, g, m và sai đối với những người khác.

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

• Xác định cấu trúc nút, có một mảng gồm 26 nút và cờ isEnd

• ban đầu isEnd là false và mảng con được điền bằng null.

• Xác định đầu nút

• Tạo một mảng các nút WaitList

• Xác định một hàm insertNode (), điều này sẽ lấy head, s,

  • curr:=đầu

  • để khởi tạo i:=0, khi i

    • x:=s [i]

    • nếu con [x - 'a'] của curr không phải là-null, thì -

      • curr.child [x - 'a'] =tạo nút Node mới

    • curr:=curr.child [x - 'a']

  • isEnd of curr:=true

• Từ trình khởi tạo, hãy thực hiện việc này

  • head:=tạo một nút mới

  • để khởi tạo i:=0, khi tôi

    • insertNode (head, words [i])

  • curr:=đầu

• Xác định một truy vấn hàm (), điều này sẽ lấy x,

  • tạo một mảng các nút tạm thời

  • nếu head.child [x - 'a'], thì -

    • chèn đầu vào cuối danh sách chờ

  • ret:=false

  • để khởi tạo i:=0, khi tôi

    • curr:=waitList [i]

    • nếu curr.child [x - 'a'], thì

      • curr:=child [x - 'a'] của curr

      • chèn cuộn tóc vào cuối nhiệt độ

      • ret:=ret OR isEnd of curr

  • hoán đổi (tạm thời, danh sách chờ)

  • 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;
struct Node {
   Node* child[26];
   bool isEnd;
   Node(){
      isEnd = false;
      for (int i = 0; i < 26; i++)
      child[i] = NULL;
   }
};
class StreamChecker {
   public:
   Node* head;
   vector<Node*> waitList;
   void insertNode(Node* head, string& s){
      Node* curr = head;
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         if (!curr->child[x - 'a']) {
            curr->child[x - 'a'] = new Node();
         }
         curr = curr->child[x - 'a'];
      }
      curr->isEnd = true;
   }
   StreamChecker(vector<string>& words){
      head = new Node();
      for (int i = 0; i < words.size(); i++) {
         insertNode(head, words[i]);
      }
      Node* curr = head;
   }
   bool query(char x){
      vector<Node*> temp;
      if (head->child[x - 'a']) {
         waitList.push_back(head);
      }
      bool ret = false;
      for (int i = 0; i < waitList.size(); i++) {
         Node* curr = waitList[i];
         if (curr->child[x - 'a']) {
            curr = curr->child[x - 'a'];
            temp.push_back(curr);
            ret |= curr->isEnd;
         }
      }
      swap(temp, waitList);
      return ret;
   }
};
main(){
   vector<string> v = {"ce","g","lm"};
   StreamChecker ob(v);
   cout << (ob.query('a')) << endl;
   cout << (ob.query('b')) << endl;
   cout << (ob.query('c')) << endl;
   cout << (ob.query('e')) << endl;
   cout << (ob.query('f')) << endl;
   cout << (ob.query('g')) << endl;
   cout << (ob.query('h')) << endl;
   cout << (ob.query('i')) << endl;
   cout << (ob.query('j')) << endl;
   cout << (ob.query('k')) << endl;
   cout << (ob.query('l')) << endl;
   cout << (ob.query('m'));
}

Đầu vào

"ce","g","lm", query(),

Đầu ra

0 0 0 1 0 1 0 0 0 0 0 1