Количество строк, которые становятся равными одной из двух строк после одного удаления

Опубликовано: 5 Января, 2022

Учитывая две строки str1 и str2 , задача состоит в том, чтобы подсчитать все допустимые строки. Пример допустимой строки приведен ниже:
Если str1 = «игрушка» и str2 = «попробуйте» . Тогда S = «tory» является допустимой строкой, потому что, когда из нее удаляется единственный символ, то есть S = «t o ry» = «try», он становится равным str1 . Это свойство также должно быть действительным с str2, т.е. S = «to r y» = «toy» = str2.
Задача - вывести количество всех возможных допустимых строк.
Примеры:

Input: str = “toy”, str2 = “try”
Output: 2
The given two words could be obtained from either word “tory” or word “troy”. So output is 2.
Input: str1 = “sweet”, str2 = “sheep”
Output: 0
The two given word couldn’t be obtained from the same word by removing one letter.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Вычислите A как самый длинный общий префикс для str1 и str2 и C как самый длинный общий суффикс для str1 и str2 . Если обе строки равны, то возможно 26 * (n + 1) строк. В противном случае установите count = 0 и l равным первому индексу, который не является частью общего префикса, а r - крайний правый индекс, который не является частью общего суффикса.
Теперь, если str1 [l + 1… r] = str2 [l… r-1], тогда update count = count + 1 .
И если str1 [l… r-1] = str2 [l + 1… r], тогда update count = count + 1 .
Выведите счет в конце.
Ниже представлена реализация подхода:

C ++

 // C++ implementation of the approach
 #include <bits/stdc++.h>
 using namespace std;
 // Function to return the count of the
 // required strings
 int findAnswer(string str1, string str2, int n)
 {
    int l, r;
    int ans = 2; 
    // Searching index after longest common
    // prefix ends
    for ( int i = 0; i < n; ++i) {
        if (str1[i] != str2[i]) {
            l = i;
            break ;
        }
    }
    // Searching index before longest common
    // suffix ends
    for ( int i = n - 1; i >= 0; i--) {
        if (str1[i] != str2[i]) {
            r = i;
            break ;
        }
    }
    // If str1 = str2
    if (r < l)
        return 26 * (n + 1); 
    // If only 1 character is different
    // in both the strings
    else if (l == r)
        return ans;
    else { 
        // Checking remaining part of string
        // for equality
        for ( int i = l + 1; i <= r; i++) {
            if (str1[i] != str2[i - 1]) {
                ans--;
                break ;
            }
        }
        // Searching in right of string h
        // (g to h)
        for ( int i = l + 1; i <= r; i++) {
            if (str1[i - 1] != str2[i]) {
                ans--;
                break ;
            }
        }
        return ans;
    }
 }
 // Driver code
 int main()
 {
    string str1 = "toy" , str2 = "try" ;
    int n = str1.length();
    cout << findAnswer(str1, str2, n);
    return 0;
 }

Джава

 // Java implementation of the approach
 import java.util.*;
 class GFG
 {
 // Function to return the count of the
 // required strings
 static int findAnswer(String str1, String str2, int n)
 {
    int l = 0 , r = 0 ;
    int ans = 2 ; 
    // Searching index after longest common
    // prefix ends
    for ( int i = 0 ; i < n; ++i)
    {
        if (str1.charAt(i) != str2.charAt(i))
        {
            l = i;
            break ;
        }
    }
    // Searching index before longest common
    // suffix ends
    for ( int i = n - 1 ; i >= 0 ; i--)
    {
        if (str1.charAt(i) != str2.charAt(i))
        {
            r = i;
            break ;
        }
    }
    // If str1 = str2
    if (r < l)
        return 26 * (n + 1 ); 
    // If only 1 character is different
    // in both the strings
    else if (l == r)
        return ans;
    else { 
        // Checking remaining part of string
        // for equality
        for ( int i = l + 1 ; i <= r; i++)
        {
            if (str1.charAt(i) != str2.charAt(i - 1 ))
            {
                ans--;
                break ;
            }
        }
        // Searching in right of string h
        // (g to h)
        for ( int i = l + 1 ; i <= r; i++)
        {
            if (str1.charAt(i- 1 ) != str2.charAt(i))
            {
                ans--;
                break ;
            }
        }
        return ans;
    }
 }
 // Driver code
 public static void main(String args[])
 {
    String str1 = "toy" , str2 = "try" ;
    int n = str1.length();
    System.out.println(findAnswer(str1, str2, n));
    
}
 }
 // This code is contributed by
 // Surendra_Gangwar

Python3

 # Python3 implementation of the approach
 import math as mt
 # Function to return the count of
 # the required strings
 def findAnswer(str1, str2, n): 
    l, r = 0 , 0
    ans = 2 
    # Searching index after longest
    # common prefix ends
    for i in range (n):
        if (str1[i] ! = str2[i]):
            l = i
            break
        
    # Searching index before longest
    # common suffix ends
    for i in range (n - 1 , - 1 , - 1 ):
        if (str1[i] ! = str2[i]):
            r = i
            break
        
    if (r < l):
        return 26 * (n + 1 ) 
    # If only 1 character is different
    # in both the strings
    elif (l = = r):
        return ans
    else : 
        # Checking remaining part of
        # string for equality
        for i in range (l + 1 , r + 1 ):
            if (str1[i] ! = str2[i - 1 ]):
                ans - = 1
                break
            
        # Searching in right of string h
        # (g to h)
        for i in range (l + 1 , r + 1 ):
            if (str1[i - 1 ] ! = str2[i]):
                ans - = 1
                break
            
        return ans
    
# Driver code
 str1 = "toy"
 str2 = "try"
 n = len (str1)
 print (findAnswer(str1, str2, n))
 # This code is contributed
 # by Mohit kumar 29

C #

 // C# implementation of the approach
 using System;
 class GFG
 {
 // Function to return the count of the
 // required strings
 static int findAnswer( string str1, string str2, int n)
 {
    int l = 0, r = 0;
    int ans = 2; 
    // Searching index after longest common
    // prefix ends
    for ( int i = 0; i < n; ++i)
    {
        if (str1[i] != str2[i])
        {
            l = i;
            break ;
        }
    }
    // Searching index before longest common
    // suffix ends
    for ( int i = n - 1; i >= 0; i--)
    {
        if (str1[i] != str2[i])
        {
            r = i;
            break ;
        }
    }
    // If str1 = str2
    if (r < l)
        return 26 * (n + 1); 
    // If only 1 character is different
    // in both the strings
    else if (l == r)
        return ans;
    else
    {
        // Checking remaining part of string
        // for equality
        for ( int i = l + 1; i <= r; i++)
        {
            if (str1[i] != str2[i - 1])
            {
                ans--;
                break ;
            }
        }
        // Searching in right of string h
        // (g to h)
        for ( int i = l + 1; i <= r; i++)
        {
            if (str1[i-1] != str2[i])
            {
                ans--;
                break ;
            }
        }
        return ans;
    }
 }
 // Driver code
 public static void Main()
 {
    String str1 = "toy" , str2 = "try" ;
    int n = str1.Length;
    Console.WriteLine(findAnswer(str1, str2, n));
 }
 }
 // This code is contributed by
 // shs

PHP

 <?php
 // PHP implementation of the above approach
 // Function to return the count of
 // the required strings
 function findAnswer( $str1 , $str2 , $n )
 {
    $ans = 2; 
    // Searching index after longest
    // common prefix ends
    for ( $i = 0; $i < $n ; ++ $i )
    {
        if ( $str1 [ $i ] != $str2 [ $i ])
        {
            $l = $i ;
            break ;
        }
    }
    // Searching index before longest
    // common suffix ends
    for ( $i = $n - 1; $i >= 0; $i --)
    {
        if ( $str1 [ $i ] != $str2 [ $i ])
        {
            $r = $i ;
            break ;
        }
    }
    // If str1 = str2
    if ( $r < $l )
        return 26 * ( $n + 1); 
    // If only 1 character is different
    // in both the strings
    else if ( $l == $r )
        return $ans ;
    else
    {
        // Checking remaining part of string
        // for equality
        for ( $i = $l + 1; $i <= $r ; $i ++)
        {
            if ( $str1 [ $i ] != $str2 [ $i - 1])
            {
                $ans --;
                break ;
            }
        }
        // Searching in right of string h
        // (g to h)
        for ( $i = $l + 1; $i <= $r ; $i ++)
        {
            if ( $str1 [ $i - 1] != $str2 [ $i ])
            {
                $ans --;
                break ;
            }
        }
        return $ans ;
    }
 }
 // Driver code
 $str1 = "toy" ;
 $str2 = "try" ;
 $n = strlen ( $str1 );
 echo findAnswer( $str1 , $str2 , $n );
 // This code is contributed by Ryuga
 ?>

Javascript

 <script>
 // Javascript implementation of the approach
    // Function to return the count of the
    // required strings
    function findAnswer( str1, str2 , n)
    {
        var l = 0, r = 0;
        var ans = 2; 
        // Searching index after longest common
        // prefix ends
        for (i = 0; i < n; ++i) {
            if (str1.charAt(i) != str2.charAt(i))
            {
                l = i;
                break ;
            }
        }
        // Searching index before longest common
        // suffix ends
        for (i = n - 1; i >= 0; i--) {
            if (str1.charAt(i) != str2.charAt(i))
            {
                r = i;
                break ;
            }
        }
        // If str1 = str2
        if (r < l)
            return 26 * (n + 1); 
        // If only 1 character is different
        // in both the strings
        else if (l == r)
            return ans;
        else { 
            // Checking remaining part of string
            // for equality
            for (i = l + 1; i <= r; i++) {
                if (str1.charAt(i) != str2.charAt(i - 1))
                {
                    ans--;
                    break ;
                }
            }
            // Searching in right of string h
            // (g to h)
            for (i = l + 1; i <= r; i++) {
                if (str1.charAt(i - 1) != str2.charAt(i))
                {
                    ans--;
                    break ;
                }
            }
            return ans;
        }
    }
    // Driver code
    

                    
                                            Статьи
                                            Олимпиады по программированию
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИОнлайн-обменники: быстрый и удобный способ конвертации активов в современном мире
17 Апреля, 2024
Лучшие онлайн-курсы по WordPress: рейтинг 2024
29 Марта, 2024
Для кого буду полезны услуги SMS-центра
24 Марта, 2024
Что такое экспертиза исходного кода и как ее проводят?
3 Марта, 2024
Как добавить деньги на счет аккаунта Steam через криптовалюту
20 Февраля, 2024
Заказать докторскую диссертацию на заказ
30 Января, 2024
Купить лайки в ВК: зачем, сколько и где
19 Января, 2024
Как добавить деньги на свой аккаунт в Steam и начать покупать игры и контент
12 Января, 2024


    


        
            
                
                    
                        
                        < PROGLER >
                    
                
                
                    
                        Общее
                        
                        Контакты
                        Политика конфиденциальности
                    
                    
                        Обучение
                        Блог
                    
                
            
            
                © progler.ru 2024. Все права защищены.