检查给定链表中是否存在字符串作为子序列

---

在这个问题中，我们将检查链表是否包含该字符串作为子序列。我们可以迭代链表和字符串来检查链表中是否存在字符串作为子序列。

问题陈述 − 我们给定一个大小为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++ 代码来检查链表中是否存在字符串作为子序列。程序员还可以编写代码来检查给定字符串是否作为子序列存在于链表中。