Рубрики

Мета-строки (проверьте, могут ли две строки стать одинаковыми после перестановки в одной строке)

Учитывая две строки, задача состоит в том, чтобы проверить, являются ли эти строки мета-строками или нет. Мета-строки — это строки, которые можно сделать равными ровно одним обменом в любой из строк. Равные строки здесь не рассматриваются как мета-строки.

Примеры:

Input : str1 = "geeks" 
        str2 = "keegs"
Output : Yes
By just swapping 'k' and 'g' in any of string, 
both will become same.

Input : str1 = "rsting"
        str2 = "string
Output : No

Input :  str1 = "Converse"
         str2 = "Conserve"

Спросил в: Google

Ниже приведены шаги, используемые в алгоритме.

  1. Проверьте, имеют ли обе строки одинаковую длину или нет, если не возвращает false.
  2. В противном случае, начните сравнивать как строки, так и счетчик количества несопоставленных символов, а также сохранить индекс несопоставленных символов.
  3. Если несопоставленные символы больше 2, вернуть false.
  4. В противном случае проверьте, будет ли при замене любого из этих двух символов в любой строке строка равной или нет.
  5. Если да, тогда верните истину. В противном случае верните false.

C ++

// C ++ программа для проверки, являются ли две строки мета-строками
#include<iostream>

using namespace std;

  
// Возвращает true, если str1 и str2 являются мета-строками

bool areMetaStrings(string str1, string str2)

{

    int len1 = str1.length();

    int len2 = str2.length();

  

    // Возвращаем false, если оба не равны по длине

    if (len1 != len2)

        return false;

  

    // Для хранения индексов ранее не совпадали

    // персонажи

    int prev = -1, curr = -1;

  

    int count = 0;

    for (int i=0; i<len1; i++)

    {

        // Если текущий символ не совпадает

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

        {

            // Подсчитать количество не совпадающих символов

            count++;

  

            // Если несоответствие больше 2,

            // затем возвращаем false

            if (count > 2)

                return false;

  

            // Сохраняем оба непревзойденных символа

            // обе строки

            prev = curr;

            curr = i;

        }

    }

  

    // Проверяем, не соответствует ли предыдущий элемент string1

    // равно curr, не совпадающему с string2

    // а также проверяем наличие уникального символа curr,

    // если оба одинаковы, возвращаем true

    return (count == 2 &&

            str1[prev] == str2[curr] &&

            str1[curr] == str2[prev]);

}

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

int main()

{

    string str1 = "converse";

    string str2 = "conserve";

  

    areMetaStrings(str1,str2) ? cout << "Yes"

                            : cout << "No";

    return 0;

}

Джава

// Java program to check if two strings are meta strings

  
class Test
{

    // Returns true if str1 and str2 are meta strings

    static boolean areMetaStrings(String str1, String str2)

    {

        int len1 = str1.length();

        int len2 = str2.length();

       

        // Return false if both are not of equal length

        if (len1 != len2)

            return false;

       

        // To store indexes of previously mismatched

        // characters

        int prev = -1, curr = -1;

       

        int count = 0;

        for (int i=0; i<len1; i++)

        {

            // If current character doesn't match

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

            {

                // Count number of unmatched character

                count++;

       

                // If unmatched are greater than 2,

                // then return false

                if (count > 2)

                    return false;

       

                // Store both unmatched characters of

                // both strings

                prev = curr;

                curr = i;

            }

        }

       

        // Check if previous unmatched of string1

        // is equal to curr unmatched of string2

        // and also check for curr unmatched character,

        // if both are same, then return true

        return (count == 2 &&

                str1.charAt(prev) == str2.charAt(curr) &&

                str1.charAt(curr) == str2.charAt(prev));

    }

      

    // Driver method

    public static void main(String args[])

    {

        String str1 = "converse";

        String str2 = "conserve";

       

        System.out.println(areMetaStrings(str1,str2) ? "Yes" :"No");

    }

}

питон

# Программа Python для проверки наличия двух строк
# мета-строки

  
# Возвращает true, если str1 и str2 являются мета-строками

def areMetaStrings( str1, str2) :

    len1 = len(str1)

    len2 = len(str2)

        

    # Вернуть false, если оба не равны по длине

    if (len1 != len2) :

        return False

        

    # Для хранения индексов ранее не соответствовал

    # персонажи

    prev = -1

    curr = -1

        

    count = 0 

    i = 0

    while i < len1 :

              

        # Если текущий символ не совпадает

        if (str1[i] != str2[i] ) :

         

        # Подсчитать количество непревзойденных символов

            count = count + 1

        

            # Если несоответствие больше 2,

            # затем вернуть false

            if (count > 2) :

                return False

        

            # Храните оба непревзойденных символа

            # обе строки

            prev = curr

            curr = i

              

        i = i + 1

        

    # Проверить, если предыдущий не соответствует строки1

    # равно curr не соответствует string2

    # а также проверить наличие непревзойденного символа,

    # если оба одинаковы, вернуть true

    return (count == 2 and str1[prev] == str2[curr]

               and str1[curr] == str2[prev])

      
# Метод драйвера

str1 = "converse"

str2 = "conserve"

if ( areMetaStrings(str1,str2) ) :

     print "Yes" 

else:

    print "No"

      
# Этот код предоставлен Никитой Тивари.

C #

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

using System;

  

class GFG {

      

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

    // являются мета-строками

    static bool areMetaStrings(String str1,

                                String str2)

    {

        int len1 = str1.Length;

        int len2 = str2.Length;

      

        // Возвращаем false, если оба не

        // равной длины

        if (len1 != len2)

            return false;

      

        // Для хранения индексов ранее

        // несоответствующие символы

        int prev = -1, curr = -1;

      

        int count = 0;

        for (int i = 0; i < len1; i++)

        {

              

            // Если текущий символ

            // не соответствует

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

            {

                  

                // Подсчитать количество не найденных

                // персонаж

                count++;

      

                // Если больше нет

                // чем 2, затем возвращаем false

                if (count > 2)

                    return false;

      

                // Сохраняем оба непревзойденных

                // символы обеих строк

                prev = curr;

                curr = i;

            }

        }

      

        // Проверяем, если предыдущий не соответствует

        // string1 равно curr unmatched

        // из string2, а также проверка на curr

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

        // то же самое, затем возвращаем true

        return (count == 2 &&

                 str1[prev] == str2[curr] &&

                   str1[curr] == str2[prev]);

    }

      

    // Метод драйвера

    public static void Main()

    {

        String str1 = "converse";

        String str2 = "conserve";

      

        Console.WriteLine(

            areMetaStrings(str1,str2) 

                       ? "Yes" :"No");

    }

}

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

PHP

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

  
// Возвращает true, если str1 и str2
// мета строки

function areMetaStrings($str1, $str2)

{

    $len1 = strlen($str1);

    $len2 = strlen($str1);

  

    // Возвращаем false, если оба не

    // равной длины

    if ($len1 != $len2)

        return false;

  

    // Для хранения индексов ранее

    // несоответствующие символы

    $prev = -1; $curr = -1;

  

    $count = 0;

    for ($i = 0; $i < $len1; $i++)

    {

          

        // Если текущий символ

        // не соответствует

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

        {

              

            // Подсчитать количество не найденных

            // персонаж

            $count++;

  

            // Если больше нет

            // чем 2, затем возвращаем false

            if ($count > 2)

                return false;

  

            // Сохраняем оба непревзойденных

            // символы обоих

            // строки

            $prev = $curr;

            $curr = $i;

        }

    }

  

    // Проверяем, если предыдущий не соответствует

    // string1 равно curr unmatched

    // из string2, а также проверка на curr

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

    // то же самое, затем возвращаем true

    return ($count == 2 &&

            $str1[$prev] == $str2[$curr] &&

            $str1[$curr] == $str2[$prev]);

}

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

    $str1 = "converse";

    $str2 = "conserve";

  

    if(areMetaStrings($str1, $str2)) 

        echo "Yes";

    else

        echo "No";

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


Выход:

Yes

Ссылка :
https://www.careercup.com/question?id=6247626241474560

Эта статья предоставлена Сахилом Чхаброй (Акку) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Мета-строки (проверьте, могут ли две строки стать одинаковыми после перестановки в одной строке)

0.00 (0%) 0 votes