Dadas dos strings str1 y str2, encuentre si str1 es una subsecuencia de str2. Una subsecuencia es una secuencia que se puede derivar de otra secuencia eliminando algunos elementos sin cambiar el orden de los elementos restantes (fuente: wiki ). La complejidad temporal esperada es lineal.
Ejemplos:
C++
// Recursive C++ program to check
// if a string is subsequence
// of another string
#include <cstring>
#include <iostream>
using namespace std;
// Returns true if str1[] is a
// subsequence of str2[]. m is
// length of str1 and n is length of str2
bool isSubSequence(char str1[], char str2[], int m, int n)
{
// Base Cases
if (m == 0)
return true;
if (n == 0)
return false;
// If last characters of two
// strings are matching
if (str1[m - 1] == str2[n - 1])
return isSubSequence(str1, str2, m - 1, n - 1);
// If last characters are
// not matching
return isSubSequence(str1, str2, m, n - 1);
}
// Driver program to check whether str1 is subsequence of str2 or not.
int main()
{
char str1[] = "gksrek";
char str2[] = "geeksforgeeks";
int m = strlen(str1);
int n = strlen(str2);
isSubSequence(str1, str2, m, n) ? cout << "Yes "
: cout << "No";
return 0;
}
Java
// Recursive Java program to check if a string
// is subsequence of another string
import java.io.*;
class SubSequence {
// Returns true if str1[] is a subsequence of str2[]
// m is length of str1 and n is length of str2
static boolean isSubSequence(String str1, String str2,
int m, int n)
{
// Base Cases
if (m == 0)
return true;
if (n == 0)
return false;
// If last characters of two strings are matching
if (str1.charAt(m - 1) == str2.charAt(n - 1))
return isSubSequence(str1, str2, m - 1, n - 1);
// If last characters are not matching
return isSubSequence(str1, str2, m, n - 1);
}
// Driver program
public static void main(String[] args)
{
String str1 = "gksrek";
String str2 = "geeksforgeeks";
int m = str1.length();
int n = str2.length();
boolean res = isSubSequence(str1, str2, m, n);
if (res)
System.out.println("Yes");
else
System.out.println("No");
}
}
// Contributed by Pramod Kumar
Python3
# Recursive Python program to check
# if a string is subsequence
# of another string
# Returns true if str1[] is a
# subsequence of str2[].
def isSubSequence(string1, string2, m, n):
# Base Cases
if m == 0:
return True
if n == 0:
return False
# If last characters of two
# strings are matching
if string1[m-1] == string2[n-1]:
return isSubSequence(string1, string2, m-1, n-1)
# If last characters are not matching
return isSubSequence(string1, string2, m, n-1)
# Driver program to test the above function
string1 = "gksrek"
string2 = "geeksforgeeks"
if isSubSequence(string1, string2, len(string1), len(string2)):
print ("Yes")
else:
print ("No")
# This code is contributed by BHAVYA JAIN
C#
// Recursive C# program to check if a string
// is subsequence of another string
using System;
class GFG {
// Returns true if str1[] is a
// subsequence of str2[] m is
// length of str1 and n is length
// of str2
static bool isSubSequence(string str1, string str2,
int m, int n)
{
// Base Cases
if (m == 0)
return true;
if (n == 0)
return false;
// If last characters of two strings
// are matching
if (str1[m - 1] == str2[n - 1])
return isSubSequence(str1, str2, m - 1, n - 1);
// If last characters are not matching
return isSubSequence(str1, str2, m, n - 1);
}
// Driver program
public static void Main()
{
string str1 = "gksrek";
string str2 = "geeksforgeeks";
int m = str1.Length;
int n = str2.Length;
bool res = isSubSequence(str1, str2, m, n);
if (res)
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// Recursive PHP program to check
// if a string is subsequence of
// another string
// Returns true if str1[] is a
// subsequence of str2[]. m is
// length of str1 and n is
// length of str2
function isSubSequence($str1, $str2,
$m, $n)
{
// Base Cases
if ($m == 0) return true;
if ($n == 0) return false;
// If last characters of two
// strings are matching
if ($str1[$m - 1] == $str2[$n - 1])
return isSubSequence($str1, $str2,
$m - 1, $n - 1);
// If last characters
// are not matching
return isSubSequence($str1, $str2,
$m, $n - 1);
}
// Driver Code
$str1= "gksrek";
$str2 = "geeksforgeeks";
$m = strlen($str1);
$n = strlen($str2);
$t = isSubSequence($str1, $str2, $m, $n) ?
"Yes ":
"No";
if($t = true)
echo "Yes";
else
echo "No";
// This code is contributed by ajit
?>
Javascript
<script>
// Recursive Javascript program to check if
// a string is subsequence of another string
// Returns true if str1[] is a
// subsequence of str2[] m is
// length of str1 and n is length
// of str2
function isSubSequence(str1, str2, m, n)
{
// Base Cases
if (m == 0)
return true;
if (n == 0)
return false;
// If last characters of two strings
// are matching
if (str1[m - 1] == str2[n - 1])
return isSubSequence(str1, str2,
m - 1, n - 1);
// If last characters are not matching
return isSubSequence(str1, str2, m, n - 1);
}
// Driver code
let str1 = "gksrek";
let str2 = "geeksforgeeks";
let m = str1.length;
let n = str2.length;
let res = isSubSequence(str1, str2, m, n);
if (res)
document.write("Yes");
else
document.write("No");
// This code is contributed by divyesh072019
</script>
C++
/*Iterative C++ program to check
If a string is subsequence of another string*/
#include <bits/stdc++.h>
using namespace std;
/*Returns true if s1 is subsequence of s2*/
bool issubsequence(string& s1, string& s2)
{
int n = s1.length(), m = s2.length();
int i = 0, j = 0;
while (i < n && j < m) {
if (s1[i] == s2[j])
i++;
j++;
}
/*If i reaches end of s1,that mean we found all
characters of s1 in s2,
so s1 is subsequence of s2, else not*/
return i == n;
}
int main()
{
string s1 = "gksrek";
string s2 = "geeksforgeeks";
if (issubsequence(s1, s2))
cout << "gksrek is subsequence of geekforgeeks" << endl;
else
cout << "gksrek is not a subsequence of geekforgeeks" << endl;
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG
{
/*Iterative Java program to check
If a String is subsequence of another String*/
/*Returns true if s1 is subsequence of s2*/
static boolean issubsequence(String s1, String s2)
{
int n = s1.length(), m = s2.length();
int i = 0, j = 0;
while (i < n && j < m) {
if (s1.charAt(i) == s2.charAt(j))
i++;
j++;
}
/*If i reaches end of s1,that mean we found all
characters of s1 in s2,
so s1 is subsequence of s2, else not*/
return i == n;
}
public static void main(String args[])
{
String s1 = "gksrek";
String s2 = "geeksforgeeks";
if (issubsequence(s1, s2))
System.out.println("gksrek is subsequence of geekforgeeks");
else
System.out.println("gksrek is not a subsequence of geekforgeeks");
}
}
// This code is contributed by shinjanpatra.
Python3
# Iterative JavaScript program to check
# If a string is subsequence of another string
# Returns true if s1 is subsequence of s2
def issubsequence(s1, s2):
n,m = len(s1),len(s2)
i,j = 0,0
while (i < n and j < m):
if (s1[i] == s2[j]):
i += 1
j += 1
# If i reaches end of s1,that mean we found all
# characters of s1 in s2,
# so s1 is subsequence of s2, else not
return i == n
# driver code
s1 = "gksrek"
s2 = "geeksforgeeks"
if (issubsequence(s1, s2)):
print("gksrek is subsequence of geekforgeeks")
else:
print("gksrek is not a subsequence of geekforgeeks")
# This code is contributed by shinjanpatra
C#
// C# code to implement the approach
using System;
class GFG {
/*Returns true if s1 is subsequence of s2*/
static bool issubsequence(string s1, string s2)
{
int n = s1.Length, m = s2.Length;
int i = 0, j = 0;
while (i < n && j < m) {
if (s1[i] == s2[j])
i++;
j++;
}
/*If i reaches end of s1,that mean we found all
characters of s1 in s2,
so s1 is subsequence of s2, else not*/
return i == n;
}
public static void Main(string[] args)
{
string s1 = "gksrek";
string s2 = "geeksforgeeks";
if (issubsequence(s1, s2))
Console.WriteLine(s1 + " is a subsequence of "
+ s2);
else
Console.WriteLine(
s1 + " not is a subsequence of " + s2);
}
}
// This code is contributed by phasing17.
Javascript
<script>
/*Iterative JavaScript program to check
If a string is subsequence of another string*/
/*Returns true if s1 is subsequence of s2*/
function issubsequence(s1, s2)
{
let n = s1.length, m = s2.length;
let i = 0, j = 0;
while (i < n && j < m) {
if (s1[i] == s2[j])
i++;
j++;
}
/*If i reaches end of s1,that mean we found all
characters of s1 in s2,
so s1 is subsequence of s2, else not*/
return i == n;
}
// driver code
let s1 = "gksrek";
let s2 = "geeksforgeeks";
if (issubsequence(s1, s2))
document.write("gksrek is subsequence of geekforgeeks","</br>");
else
document.write("gksrek is not a subsequence of geekforgeeks","</br>");
// This code is contributed by shinjanpatra
</script>
C++
// memoization C++ program to check
// if a string is subsequence
// of another string
#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001];
// returns the length of longest common subsequence
int isSubSequence(string& s1, string& s2, int i, int j)
{
if (i == 0 || j == 0) {
return 0;
}
if (dp[i][j] != -1) {
return dp[i][j];
}
if (s1[i - 1] == s2[j - 1]) {
return dp[i][j]
= 1 + isSubSequence(s1, s2, i - 1, j - 1);
}
else {
return dp[i][j] = isSubSequence(s1, s2, i, j - 1);
}
}
/* Driver program to test above function */
int main()
{
string str1 = "gksrek";
string str2 = "geeksforgeeks";
int m = str1.size();
int n = str2.size();
if (m > n) {
cout << "NO" << endl;
return 0;
}
dp[m][n];
memset(dp, -1, sizeof(dp));
if (isSubSequence(str1, str2, m, n) == m) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
return 0;
}
// this code is contributed by Arun Bang
Java
// memoization Java program to check
// if a string is subsequence
// of another string
class GFG {
public static int[][] dp = new int[1001][1001];
// returns the length of longest common subsequence
public static int isSubSequence(String s1, String s2,
int i, int j)
{
if (i == 0 || j == 0) {
return 0;
}
if (dp[i][j] != -1) {
return dp[i][j];
}
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
return dp[i][j]
= 1 + isSubSequence(s1, s2, i - 1, j - 1);
}
else {
return dp[i][j]
= isSubSequence(s1, s2, i, j - 1);
}
}
/* Driver program to test above function */
public static void main(String[] args)
{
String str1 = "gksrek";
String str2 = "geeksforgeeks";
int m = str1.length();
int n = str2.length();
if (m > n) {
System.out.println("NO");
}
for (int i = 0; i <= 1000; i++) {
for (int j = 0; j <= 1000; j++)
dp[i][j] = -1;
}
if (isSubSequence(str1, str2, m, n) == m) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
}
}
// This code is contributed by phasing17
Python3
# memoization Python program to check
# if a string is subsequence
# of another string
dp = [[-1]*1001]*1001
# returns the length of longest common subsequence
def isSubSequence(s1,s2,i,j):
if (i == 0 or j == 0):
return 0
if (dp[i][j] != -1):
return dp[i][j]
if (s1[i - 1] == s2[j - 1]):
dp[i][j] = 1 + isSubSequence(s1, s2, i - 1, j - 1)
return dp[i][j]
else:
dp[i][j] = isSubSequence(s1, s2, i, j - 1)
return dp[i][j]
# Driver program to test above function
str1 = "gksrek"
str2 = "geeksforgeeks"
m = len(str1)
n = len(str2)
if (m > n):
print("NO")
if (isSubSequence(str1, str2, m, n) == m):
print("YES")
else:
print("NO")
# this code is contributed by shinjanpatra
C#
// memoization C# program to check
// if a string is subsequence
// of another string
using System;
public class GFG {
public static int[, ] dp = new int[1001, 1001];
// returns the length of longest common subsequence
public static int isSubSequence(string s1, string s2,
int i, int j)
{
if (i == 0 || j == 0) {
return 0;
}
if (dp[i, j] != -1) {
return dp[i, j];
}
if (s1[i - 1] == s2[j - 1]) {
return dp[i, j]
= 1 + isSubSequence(s1, s2, i - 1, j - 1);
}
else {
return dp[i, j]
= isSubSequence(s1, s2, i, j - 1);
}
}
// Driver Code
public static void Main(string[] args)
{
string str1 = "gksrek";
string str2 = "geeksforgeeks";
int m = str1.Length;
int n = str2.Length;
if (m > n) {
Console.WriteLine("NO");
}
for (int i = 0; i <= 1000; i++) {
for (int j = 0; j <= 1000; j++)
dp[i, j] = -1;
}
if (isSubSequence(str1, str2, m, n) == m) {
Console.WriteLine("YES");
}
else {
Console.WriteLine("NO");
}
}
}
// This code is contributed by phasing17
Javascript
<script>
// memoization JavaScript program to check
// if a let is subsequence
// of another let
let dp = new Array(1001).fill(-1).map(() => new Array(1001).fill(-1));
// returns the length of longest common subsequence
const isSubSequence = (s1, s2, i, j) => {
if (i == 0 || j == 0) {
return 0;
}
if (dp[i][j] != -1) {
return dp[i][j];
}
if (s1[i - 1] == s2[j - 1]) {
return dp[i][j]
= 1 + isSubSequence(s1, s2, i - 1, j - 1);
}
else {
return dp[i][j] = isSubSequence(s1, s2, i, j - 1);
}
}
/* Driver program to test above function */
let str1 = "gksrek";
let str2 = "geeksforgeeks";
let m = str1.length;
let n = str2.length;
if (m > n)
document.write("NO<br/>");
if (isSubSequence(str1, str2, m, n) == m) {
document.write("YES<br/>");
}
else {
document.write("NO<br/>");
}
// This code is contributed by rakeshsahni
</script>
C++
// Iterative C++ program to check
// if a string is subsequence
// of another string
#include <cstring>
#include <iostream>
using namespace std;
// Returns true if str1[] is a
// subsequence of str2[]. m is
// length of str1 and n is length of str2
bool isSubSequence(char str1[], char str2[], int m, int n)
{
int j = 0; // For index of str1 (or subsequence
// Traverse str2 and str1, and
// compare current character
// of str2 with first unmatched char
// of str1, if matched
// then move ahead in str1
for (int i = 0; i < n && j < m; i++)
if (str1[j] == str2[i])
j++;
// If all characters of str1 were found in str2
return (j == m);
}
// Driver program to test methods of graph class
int main()
{
char str1[] = "gksrek";
char str2[] = "geeksforgeeks";
int m = strlen(str1);
int n = strlen(str2);
isSubSequence(str1, str2, m, n) ? cout << "Yes "
: cout << "No";
return 0;
}
Java
// Iterative Java program to check if a string
// is subsequence of another string
import java.io.*;
class GFG {
// Returns true if str1[] is a subsequence
// of str2[] m is length of str1 and n is
// length of str2
static boolean isSubSequence(String str1, String str2,
int m, int n)
{
int j = 0;
// Traverse str2 and str1, and compare
// current character of str2 with first
// unmatched char of str1, if matched
// then move ahead in str1
for (int i = 0; i < n && j < m; i++)
if (str1.charAt(j) == str2.charAt(i))
j++;
// If all characters of str1 were found
// in str2
return (j == m);
}
// Driver program to test methods of
// graph class
public static void main(String[] args)
{
String str1 = "gksrek";
String str2 = "geeksforgeeks";
int m = str1.length();
int n = str2.length();
boolean res = isSubSequence(str1, str2, m, n);
if (res)
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Pramod Kumar
Python3
# Iterative Python program to check if a
# string is subsequence of another string
# Returns true if str1 is a subsequence of str2
def isSubSequence(str1, str2):
m = len(str1)
n = len(str2)
j = 0 # Index of str1
i = 0 # Index of str2
# Traverse both str1 and str2
# Compare current character of str2 with
# first unmatched character of str1
# If matched, then move ahead in str1
while j < m and i < n:
if str1[j] == str2[i]:
j = j+1
i = i + 1
# If all characters of str1 matched,
# then j is equal to m
return j == m
# Driver Program
str1 = "gksrek"
str2 = "geeksforgeeks"
print ("Yes" if isSubSequence(str1, str2) else "No")
# Contributed by Harshit Agrawal
C#
// Iterative C# program to check if a string
// is subsequence of another string
using System;
class GFG {
// Returns true if str1[] is a subsequence
// of str2[] m is length of str1 and n is
// length of str2
static bool isSubSequence(string str1, string str2,
int m, int n)
{
int j = 0;
// Traverse str2 and str1, and compare
// current character of str2 with first
// unmatched char of str1, if matched
// then move ahead in str1
for (int i = 0; i < n && j < m; i++)
if (str1[j] == str2[i])
j++;
// If all characters of str1 were found
// in str2
return (j == m);
}
// Driver program to test methods of
// graph class
public static void Main()
{
String str1 = "gksrek";
String str2 = "geeksforgeeks";
int m = str1.Length;
int n = str2.Length;
bool res = isSubSequence(str1, str2, m, n);
if (res)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by anuj_67.
PHP
<?php
// Iterative PHP program to check if
// a string is subsequence of another
// string
// Returns true if str1[] is
// a subsequence of str2[].
// m is length of str1 and n
// is length of str2
function isSubSequence($str1, $str2,
$m, $n)
{
// For index of str1
$j = 0;
// Traverse str2 and str1,
// and compare current
// character of str2 with
// first unmatched char of
// str1, if matched then
// move ahead in str1
for($i = 0; $i < $n and
$j < $m; $i++)
if ($str1[$j] == $str2[$i])
$j++;
// If all characters of
// str1 were found in str2
return ($j == $m);
}
// Driver Code
$str1 = "gksrek";
$str2 = "geeksforgeeks";
$m = strlen($str1);
$n = strlen($str2);
if(isSubSequence($str1, $str2, $m, $n))
echo "Yes ";
else
echo "No";
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Iterative Javascript program to check if a string
// is subsequence of another string
// Returns true if str1[] is a subsequence
// of str2[] m is length of str1 and n is
// length of str2
function isSubSequence(str1, str2, m, n)
{
let j = 0;
// Traverse str2 and str1, and compare
// current character of str2 with first
// unmatched char of str1, if matched
// then move ahead in str1
for (let i = 0; i < n && j < m; i++)
if (str1[j] == str2[i])
j++;
// If all characters of str1 were found
// in str2
return (j == m);
}
let str1 = "gksrek";
let str2 = "geeksforgeeks";
let m = str1.length;
let n = str2.length;
let res = isSubSequence(str1, str2, m, n);
if(res)
document.write("Yes");
else
document.write("No");
// This code is contributed by decode2207.
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA