检查给定链接列表中是否存在字符串作为子序列
data structurec++server side programming
在此问题中，我们将检查链接列表是否包含字符串作为子序列。我们可以一起迭代列表和字符串，以检查链接列表中是否存在字符串作为子序列。
问题陈述 - 我们给出了一个大小为 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 - 使用起始节点初始化"当前"节点，用 0 初始化"p"，用字符串的长度初始化"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;
// 创建 struct listNode
struct ListNode {
int ch;
ListNode *next;
};
// 将节点添加到链接列表
void addNode(struct ListNode **start, int ch) {
// 创建新节点
struct ListNode *temp = new struct ListNode();
// 将 ch 添加到节点
temp->ch = ch;
temp->next = NULL;
// 如果列表为空，则将节点添加到列表
if (*start == NULL) {
*start = temp;
} else {
// 如果列表有一些节点，则将节点附加到列表末尾
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();
// 同时遍历列表和字符串
while (p < len && current) {
// 如果列表中的字符和字符串的第 p 个索引处的字符相同，则将 p 加 1。
if (Str[p] == current->ch) {
p += 1;
}
// 移动到下一个节点
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;
// 创建一个空的链接列表
struct ListNode *start = NULL;
len = sizeof(list) / sizeof(list[0]);
// 将数组的字符插入到链接列表中
for (p = 0; p < len; p++)
addNode(&start, list[p]);
bool res = isSubSeqPresent(start,str);
if(res){
cout << "给定的字符串作为列表中的子序列存在。" << endl;
} else {
cout << "给定的字符串不是列表中的子序列。" << endl;
}
return 0;
}
输出
给定的字符串是列表中的子序列。
时间复杂度− O(N + K)，其中 N 是字符串的长度，K 是链接列表的长度。
空间复杂度− O(1)，因为我们不使用任何额外空间。
我们学习了编写 C++ 代码来检查字符串是否是链接列表中的子序列。程序员还可以编写代码来检查给定的字符串是否是链接列表中的子序列。
