Рубрики

По заданным двум строкам найдите, является ли первая строка подпоследовательностью второй.

По двум строкам str1 и str2 найдите, является ли str1 подпоследовательностью str2. Подпоследовательность — это последовательность, которая может быть получена из другой последовательности удаление некоторых элементов без изменения порядка оставшихся элементов (источник: вики ). Ожидаемая сложность по времени линейна.

Примеры :

Input: str1 = "AXY", str2 = "ADXCPY"
Output: True (str1 is a subsequence of str2)

Input: str1 = "AXY", str2 = "YADXCP"
Output: False (str1 is not a subsequence of str2)

Input: str1 = "gksrek", str2 = "geeksforgeeks"
Output: True (str1 is a subsequence of str2)

Идея проста: мы пересекаем обе строки с одной стороны на другую (скажем, от крайнего правого символа к крайнему левому). Если мы находим соответствующий символ, мы продвигаемся вперед в обеих строках. В противном случае мы продвигаемся только в str2.

Следующее — Рекурсивная Реализация вышеупомянутой идеи.

C / C ++

// Рекурсивная программа C ++ для проверки, является ли строка подпоследовательностью другой строки
#include<iostream>
#include<cstring>

using namespace std;

  
// Возвращает true, если str1 [] является подпоследовательностью str2 []. м является
// длина str1 и n длина str2

bool isSubSequence(char str1[], char str2[], int m, int n)

{

    // Базовые случаи

    if (m == 0) return true;

    if (n == 0) return false;

  

    // Если последние символы двух строк совпадают

    if (str1[m-1] == str2[n-1])

        return isSubSequence(str1, str2, m-1, n-1);

  

    // Если последние символы не совпадают

    return isSubSequence(str1, str2, m, n-1);

}

  
// Программа драйвера для тестирования методов класса графа

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-программа для проверки наличия строки
// является подпоследовательностью другой строки

import java.io.*;

  

class SubSequence

{

    // Возвращает true, если str1 [] является подпоследовательностью str2 []

    // m это длина str1, а n это длина str2

    static boolean isSubSequence(String str1, String str2, int m, int n)

    {

        // Базовые случаи

        if (m == 0

            return true;

        if (n == 0

            return false;

              

        // Если последние символы двух строк совпадают

        if (str1.charAt(m-1) == str2.charAt(n-1))

            return isSubSequence(str1, str2, m-1, n-1);

  

        // Если последние символы не совпадают

        return isSubSequence(str1, str2, m, n-1);

    }

      

    // Драйвер программы

    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");

    }

}

  
// Предоставлено Прамод Кумар

питон

# Рекурсивная программа на Python, чтобы проверить, является ли строка подпоследовательностью
# другой строки

  
# Возвращает true, если str1 [] является подпоследовательностью str2 []. м является
# длина str1 и n длина str2

def isSubSequence(string1, string2, m, n):

    # Базовые случаи

    if m == 0:    return True

    if n == 0:    return False

  

    # Если последние символы двух строк совпадают

    if string1[m-1] == string2[n-1]:

        return isSubSequence(string1, string2, m-1, n-1)

  

    # Если последние символы не совпадают

    return isSubSequence(string1, string2, m, n-1)

  
# Драйвер программы для проверки вышеуказанной функции

string1 = "gksrek"

string2 = "geeksforgeeks"

m = len(string1)

n = len(string2)

if isSubSequence(string1, string2, m, n):

    print "Yes"

else:

    print "No"

  
# Этот код предоставлен BHAVYA JAIN

C #

// Рекурсивная C # программа для проверки наличия строки
// является подпоследовательностью другой строки

using System;

  

class GFG {

      

    // Возвращает true, если str1 [] является

    // подпоследовательность str2 [] m

    // длина str1 и n длина

    // из str2

    static bool isSubSequence(string str1,

                  string str2, int m, int n)

    {

          

        // Базовые случаи

        if (m == 0) 

            return true;

        if (n == 0) 

            return false;

              

        // Если последние символы двух строк

        // совпадают

        if (str1[m-1] == str2[n-1])

            return isSubSequence(str1, str2,

                                    m-1, n-1);

  

        // Если последние символы не совпадают

        return isSubSequence(str1, str2, m, n-1);

    }

      

    // Драйвер программы

    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");

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Рекурсивная PHP-программа для проверки
// если строка является подпоследовательностью
// другая строка

  
// Возвращает true, если str1 [] является
// подпоследовательность str2 []. м является
// длина str1 и n
// длина str2

  

function isSubSequence($str1, $str2

                             $m, $n)

{

    // Базовые случаи

    if ($m == 0) return true;

    if ($n == 0) return false;

  

    // Если последние два символа

    // строки совпадают

    if ($str1[$m - 1] == $str2[$n - 1])

        return isSubSequence($str1, $str2,

                          $m - 1, $n - 1);

  

    // Если последние символы

    // не совпадают

    return isSubSequence($str1, $str2

                          $m, $n - 1);

}

  
// Код драйвера

$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";

  
// Этот код предоставлен ajit
?>


Выход :

Yes

Ниже приводится итерационная реализация :

C / C ++

// Итеративная программа C ++ для проверки, является ли строка подпоследовательностью другой строки
#include<iostream>
#include<cstring>

using namespace std;

  
// Возвращает true, если str1 [] является подпоследовательностью str2 []. м является
// длина str1 и n длина str2

bool isSubSequence(char str1[], char str2[], int m, int n)

{

   int j = 0; // Для индекса str1 (или подпоследовательности

  

   // Обход str2 и str1 и сравнение текущего символа

   // из str2 с первым несопоставленным символом из str1, если соответствует

   // затем двигаться вперед в str1

   for (int i=0; i<n&&j<m; i++)

       if (str1[j] == str2[i])

         j++;

  

   // Если все символы str1 были найдены в str2

   return (j==m);

}

  
// Программа драйвера для тестирования методов класса графа

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-программа для проверки наличия строки
// является подпоследовательностью другой строки

import java.io.*;

  

class GFG {

      

    // Возвращает true, если str1 [] является подпоследовательностью

    // из str2 [] m - это длина str1, а n - это

    // длина str2

    static boolean isSubSequence(String str1, 

                    String str2, int m, int n)

    {

        int j = 0;

          

        // Обходим str2 и str1 и сравниваем

        // текущий символ str2 с первым

        // несоответствующий символ str1, если совпадает

        // затем двигаться вперед в str1

        for (int i = 0; i < n && j < m; i++)

            if (str1.charAt(j) == str2.charAt(i))

                j++;

  

        // Если все символы str1 были найдены

        // в str2

        return (j == m); 

    }

      

    // Программа драйвера для тестирования методов

    // класс графика

    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");

    }

}

  
// Этот код предоставлен Pramod Kumar

питон

# Итеративная программа Python для проверки, является ли строка подпоследовательностью другой строки

  
# Возвращает true, если str1 является подпоследовательностью str2
# m длина str1, n длина str2

def isSubSequence(str1,str2,m,n):

      

    j = 0    # Индекс str1

    i = 0    # Индекс str2

      

    # Пройдите как str1, так и str2

    # Сравнить текущий символ str2 с

    # первый непревзойденный символ str1

    # Если соответствует, то двигаться вперед в str1

      

    while j<m and i<n:

        if str1[j] == str2[i]:    

            j = j+1    

        i = i + 1

          

    # Если все символы строки str1 совпадают, то j равно m

    return j==m

      
# Драйверная программа

  

str1 = "gksrek"

str2 = "geeksforgeeks"

m = len(str1)

n = len(str2)

  

print "Yes" if isSubSequence(str1,str2,m,n) else "No"

  
# Предоставлено Харшитом Агравалом

C #

// Итеративная программа на C # для проверки наличия строки
// является подпоследовательностью другой строки

using System;

  

class GFG {

      

    // Возвращает true, если str1 [] является подпоследовательностью

    // из str2 [] m - это длина str1, а n - это

    // длина str2

    static bool isSubSequence(string str1, 

                     string str2, int m, int n)

    {

        int j = 0;

          

        // Обходим str2 и str1 и сравниваем

        // текущий символ str2 с первым

        // несоответствующий символ str1, если совпадает

        // затем двигаться вперед в str1

        for (int i = 0; i < n && j < m; i++)

            if (str1[j] == str2[i])

                j++;

  

        // Если все символы str1 были найдены

        // в str2

        return (j == m); 

    }

      

    // Программа драйвера для тестирования методов

    // класс графика

    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");

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// Итеративная PHP-программа для проверки
// строка является подпоследовательностью другого
// строка

  
// Возвращает true, если str1 []
// подпоследовательность str2 [].
// m длина str1 и n
// длина str2

function isSubSequence($str1, $str2,

                             $m, $n)

{

    // Для индекса str1

    $j = 0; 

      

    // Пройдите через str2 и str1,

    // и сравниваем текущий

    // персонаж str2 с

    // первый непревзойденный символ

    // str1, если соответствует

    // двигаться вперед в str1

    for($i = 0; $i < $n and

        $j < $m; $i++)

        if ($str1[$j] == $str2[$i])

            $j++;

      

    // Если все символы

    // str1 были найдены в str2

    return ($j == $m);

}

  

    // Код драйвера

    $str1 = "gksrek";

    $str2 = "geeksforgeeks";

    $m = strlen($str1);

    $n = strlen($str2);

      

    if(isSubSequence($str1, $str2, $m, $n))

        echo "Yes ";

    else

        echo "No";

  
// Этот код предоставлен anuj_67.
?>


Выход:

Yes

Спросил в: Акколите , Теско

Сложность времени обеих реализаций выше — O (n), где n — длина str2.

Эта статья предоставлена Сачин Гупта . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

По заданным двум строкам найдите, является ли первая строка подпоследовательностью второй.

0.00 (0%) 0 votes