檢查給定連結串列中是否存在字串作為子序列

---

在這個問題中，我們將檢查連結串列是否包含該字串作為子序列。我們可以迭代連結串列和字串來檢查連結串列中是否存在字串作為子序列。

問題陳述 − 我們給定一個大小為N的字串。此外，我們還給定一個包含字母字元的動態長度連結串列。我們需要檢查連結串列是否包含該字串作為子序列。

示例

輸入

'e' -> 'h' -> 'e' -> 'k' -> 'h' -> 'e' -> 'l' ->'o' -> 'l' -> 'o' -> 'a', str = ‘hello’

輸出

Yes

解釋 − 連結串列包含該字串作為子序列。

輸入

a’ -> ‘b’ -> ‘d’ -> ‘m’ -> ‘n’ -> ‘p’ -> ‘o’ -> ‘l’, str = “hello”

輸出

No

解釋 − 連結串列不包含該字串作為子串。

輸入

a’ -> ‘a’, str = ‘aaaaa’

輸出

No

解釋 − 字串長度為5，連結串列僅包含2個節點。因此，連結串列不可能包含該字串作為子序列。

方法1

在這種方法中，我們將從字元陣列建立一個連結串列。之後，我們將匹配字串的下一個字元和節點的當前字元。如果兩者匹配，則我們移動到字串的下一個字元和連結串列中的下一個節點。否則，我們只移動到連結串列的下一個節點。透過這種方式，我們可以檢查連結串列中是否存在該字串。

演算法

步驟1 − 透過將節點插入連結串列來從陣列建立連結串列。

步驟2 − 將“current”節點初始化為起始節點，“p”初始化為0，“len”初始化為字串的長度。

步驟3 − 進行迭代，直到 p < len 且當前節點不為空。

步驟4 − 如果 Str[p] == current->ch 為真，則將“p”的值增加1。

步驟5 − 移動到連結串列的下一個節點。

步驟6 − 如果 p 等於“len”，則返回 true。

步驟7 − 在函式結束時，返回 true。

示例

#include <bits/stdc++.h>
using namespace std;

// creating the struct listNode
struct ListNode {
    int ch;
    ListNode *next;
};
// adding nodes to the linked list
void addNode(struct ListNode **start, int ch) {
    // creating a new node
    struct ListNode *temp = new struct ListNode();
    // add ch to the node
    temp->ch = ch;
    temp->next = NULL;
    // If the list is empty, add a node to the list
    if (*start == NULL) {
        *start = temp;
    } else {
        // If the list has some nodes, append the node at the end of the list
        struct ListNode *pointer1 = *start;
        while (pointer1->next != NULL)
        {
            pointer1 = pointer1->next;
        }
        pointer1->next = temp;
    }
}
bool isSubSeqPresent(ListNode *start, string Str) {
    ListNode *current = start;
    int p = 0, len = Str.size();
    //  Traverse the list and string simultaneously
    while (p < len && current) {
        // If a character in the list and at the pth index of the string is the same, increment p by 1.
        if (Str[p] == current->ch) {
            p += 1;
        }
        // Move to the next node
        current = current->next;
    }
    if (p == len) {
        return true;
    }
    return false;
}
int main() {
    int list[] = {'e', 'h', 'e', 'k', 'h', 'e', 'l', 'o', 'l', 'o', 'a'};
    string str = "hello";
    int len, p;
    // create an empty linked list
    struct ListNode *start = NULL;
    len = sizeof(list) / sizeof(list[0]);
    // inserting characters of the array to a linked list
    for (p = 0; p < len; p++)
        addNode(&start, list[p]);
   bool res = isSubSeqPresent(start,str);
   if(res){
       cout << "The given string is present as a subsequence in the list." << endl;
   } else {
       cout << "The given string is not present as a subsequence in the list." << endl;
   }
    return 0;
}

輸出

The given string is present as a subsequence in the list.

時間複雜度− O(N + K)，其中 N 是字串的長度，K 是連結串列的長度。

空間複雜度− O(1)，因為我們沒有使用任何額外的空間。

我們學習瞭如何編寫 C++ 程式碼來檢查連結串列中是否存在字串作為子序列。程式設計師還可以編寫程式碼來檢查給定字串是否作為子序列存在於連結串列中。