Dada una string S, la tarea es verificar si el objetivo de la string es una subsecuencia de la string S o no, usando un Stack .
Ejemplos:
Entrada: S = ”KOTTAYAM”, destino = ”KOTA”
Salida: Sí
Explicación: “KOTA” es una subsecuencia de “KOTTAYAM”.Entrada: S = ”GEEKSFORGEEKS”, destino =”FORFOR”
Salida: No
Enfoque: Siga los pasos para resolver el problema:
- Inicializar una pila s .
- Iterar sobre los caracteres de la string de destino .
objetivo empujado a la pila
- Atraviesa la cuerda S al revés .
- Si el carácter actual de la string S es el mismo que el carácter en la parte superior de la pila , saque el elemento superior de la pila.
Desplazamiento en S
Desplazamiento en S
Saliendo de la pila
Desplazamiento en S
Saliendo de la pila
Atravesando en st
Saliendo de la pila
Desplazamiento en S
La pila se vacía
- Si en algún momento la pila se vacía , se puede concluir que el objetivo es una subsecuencia de S.
- De lo contrario, el objetivo no es una subsecuencia de S.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if target
// is a subsequence of string S
void checkforSubsequence(string S,
string target)
{
// Declare a stack
stack<char> s;
// Push the characters of
// target into the stack
for (int i = 0; i < target.size(); i++) {
s.push(target[i]);
}
// Traverse the string S in reverse
for (int i = (int)S.size() - 1; i >= 0; i--) {
// If the stack is empty
if (s.empty()) {
cout << "Yes" << endl;
return;
}
// if S[i] is same as the
// top of the stack
if (S[i] == s.top()) {
// Pop the top of stack
s.pop();
}
}
// Stack s is empty
if (s.empty())
cout << "Yes" << endl;
else
cout << "No" << endl;
}
// Driver Code
int main()
{
string S = "KOTTAYAM";
string target = "KOTA";
checkforSubsequence(S, target);
return 0;
}
Java
// Java approach for the above approach
import java.util.Stack;
public class GFG {
// Function to check if target
// is a subsequence of string S
static void checkforSubsequence(String S, String target)
{
// Declare a stack
Stack<Character> s = new Stack<>();
// Push the characters of
// target into the stack
for (int i = 0; i < target.length(); i++) {
s.push(target.charAt(i));
}
// Traverse the string S in reverse
for (int i = (int)S.length() - 1; i >= 0; i--) {
// If the stack is empty
if (s.empty()) {
System.out.println("Yes");
return;
}
// if S[i] is same as the
// top of the stack
if (S.charAt(i) == s.peek()) {
// Pop the top of stack
s.pop();
}
}
// Stack s is empty
if (s.empty())
System.out.println("Yes");
else
System.out.println("No");
}
// Driver Code
public static void main(String[] args)
{
String S = "KOTTAYAM";
String target = "KOTA";
checkforSubsequence(S, target);
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach
# Function to check if target
# is a subsequence of string S
def checkforSubsequence(S, target):
# Declare a stack
s = []
# Push the characters of
# target into the stack
for i in range(len(target)):
s.append(target[i])
# Traverse the string S in reverse
for i in range(len(S) - 1, -1, -1):
# If the stack is empty
if (len(s) == 0):
print("Yes")
return
# If S[i] is same as the
# top of the stack
if (S[i] == s[-1]):
# Pop the top of stack
s.pop()
# Stack s is empty
if (len(s) == 0):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == "__main__":
S = "KOTTAYAM"
target = "KOTA"
checkforSubsequence(S, target)
# This code is contributed by ukasp
C#
// C# approach for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if target
// is a subsequence of string S
static void checkforSubsequence(String S,
String target)
{
// Declare a stack
Stack<char> s = new Stack<char>();
// Push the characters of
// target into the stack
for(int i = 0; i < target.Length; i++)
{
s.Push(target[i]);
}
// Traverse the string S in reverse
for(int i = (int)S.Length - 1; i >= 0; i--)
{
// If the stack is empty
if (s.Count == 0)
{
Console.WriteLine("Yes");
return;
}
// If S[i] is same as the
// top of the stack
if (S[i] == s.Peek())
{
// Pop the top of stack
s.Pop();
}
}
// Stack s is empty
if (s.Count == 0)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
// Driver Code
public static void Main(String[] args)
{
String S = "KOTTAYAM";
String target = "KOTA";
checkforSubsequence(S, target);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program for the above approach
// Function to check if target
// is a subsequence of string S
function checkforSubsequence(S, target)
{
// Declare a stack
var s = [];
// Push the characters of
// target into the stack
for (var i = 0; i < target.length; i++) {
s.push(target[i]);
}
// Traverse the string S in reverse
for (var i = S.length - 1; i >= 0; i--) {
// If the stack is empty
if (s.length==0) {
document.write( "Yes");
return;
}
// if S[i] is same as the
// top of the stack
if (S[i] == s[s.length-1]) {
// Pop the top of stack
s.pop();
}
}
// Stack s is empty
if (s.length==0)
document.write( "Yes" );
else
document.write( "No" );
}
// Driver Code
var S = "KOTTAYAM";
var target = "KOTA";
checkforSubsequence(S, target);
</script>
Producción:
Yes
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por adityamutharia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA