C++ 检查给定的链表中是否存在一个字符串作为一个子序列

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

问题陈述 − 我们有一个大小为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且当前节点为null为止。

第4步 - 如果Str[p] == current−>ch为true，则将“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++代码来检查一个字符串是否作为子序列存在于链表中。程序员也可以编写代码来检查给定的字符串是否作为子序列存在于链表中。