Видаліть символ із рядка, щоб зробити його паліндромом
Дано рядок, нам потрібно перевірити, чи можливо зробити цей рядок паліндромом після видалення рівно одного символу з нього.
приклади:
Input : str = abcba Output : Yes we can remove character ‘c’ to make string palindrome Input : str = abcbea Output : Yes we can remove character ‘e’ to make string palindrome Input : str = abecbea It is not possible to make this string palindrome just by removing one character
Ми можемо вирішити цю задачу, знайшовши позицію невідповідності. Ми починаємо цикл у рядку, зберігаючи два покажчики на обох кінцях, які переміщуються до середини після кожної ітерації. Ця ітерація зупиняється, коли ми знаходимо невідповідність, оскільки дозволено видалити лише один символ, у нас є два варіанти
У разі невідповідності або видаліть символ, на який вказує лівий вказівник, або видаліть символ, на який вказує правий вказівник.
Ми перевіримо обидва випадки, пам’ятайте, що оскільки ми пройшли однакову кількість кроків з обох сторін, цей середній рядок також має бути паліндромом після видалення одного символу, тому ми перевіряємо два підрядки, один видаливши лівий символ, а другий видаливши правий символ. Якщо один із них є паліндромом, ми можемо створити повний паліндром рядка, видаливши відповідний символ, а якщо обидва підрядки не є паліндромом, то неможливо зробити повний рядок a паліндром при заданому обмеженні.
Реалізація:
C++ // C/C++ program to check whether it is possible to make // string palindrome by removing one character #include using namespace std ; // Utility method to check if substring from low to high is // palindrome or not. bool isPalindrome ( string :: iterator low string :: iterator high ) { while ( low < high ) { if ( * low != * high ) return false ; low ++ ; high -- ; } return true ; } // This method returns -1 if it is not possible to make string // a palindrome. It returns -2 if string is already a palindrome. // Otherwise it returns index of character whose removal can // make the whole string palindrome. int possiblePalinByRemovingOneChar ( string str ) { // Initialize low and high by both the ends of the string int low = 0 high = str . length () - 1 ; // loop until low and high cross each other while ( low < high ) { // If both characters are equal then move both pointer // towards end if ( str [ low ] == str [ high ]) { low ++ ; high -- ; } else { /* If removing str[low] makes the whole string palindrome. We basically check if substring str[low+1..high] is palindrome or not. */ if ( isPalindrome ( str . begin () + low + 1 str . begin () + high )) return low ; /* If removing str[high] makes the whole string palindrome We basically check if substring str[low+1..high] is palindrome or not. */ if ( isPalindrome ( str . begin () + low str . begin () + high - 1 )) return high ; return -1 ; } } // We reach here when complete string will be palindrome // if complete string is palindrome then return mid character return -2 ; } // Driver code to test above methods int main () { string str = 'abecbea' ; int idx = possiblePalinByRemovingOneChar ( str ); if ( idx == -1 ) cout < < 'Not Possible n ' ; else if ( idx == -2 ) cout < < 'Possible without removing any character' ; else cout < < 'Possible by removing character' < < ' at index ' < < idx < < ' n ' ; return 0 ; }
Java // Java program to check whether // it is possible to make string // palindrome by removing one character import java.util.* ; class GFG { // Utility method to check if // substring from low to high is // palindrome or not. static boolean isPalindrome ( String str int low int high ) { while ( low < high ) { if ( str . charAt ( low ) != str . charAt ( high )) return false ; low ++ ; high -- ; } return true ; } // This method returns -1 if it is // not possible to make string a palindrome. // It returns -2 if string is already // a palindrome. Otherwise it returns // index of character whose removal can // make the whole string palindrome. static int possiblePalinByRemovingOneChar ( String str ) { // Initialize low and right // by both the ends of the string int low = 0 high = str . length () - 1 ; // loop until low and // high cross each other while ( low < high ) { // If both characters are equal then // move both pointer towards end if ( str . charAt ( low ) == str . charAt ( high )) { low ++ ; high -- ; } else { /* * If removing str[low] makes the * whole string palindrome. We basically * check if substring str[low+1..high] * is palindrome or not. */ if ( isPalindrome ( str low + 1 high )) return low ; /* * If removing str[high] makes the whole string * palindrome. We basically check if substring * str[low+1..high] is palindrome or not. */ if ( isPalindrome ( str low high - 1 )) return high ; return - 1 ; } } // We reach here when complete string // will be palindrome if complete string // is palindrome then return mid character return - 2 ; } // Driver Code public static void main ( String [] args ) { String str = 'abecbea' ; int idx = possiblePalinByRemovingOneChar ( str ); if ( idx == - 1 ) System . out . println ( 'Not Possible' ); else if ( idx == - 2 ) System . out . println ( 'Possible without ' + 'removing any character' ); else System . out . println ( 'Possible by removing' + ' character at index ' + idx ); } } // This code is contributed by // sanjeev2552
Python3 # Python program to check whether it is possible to make # string palindrome by removing one character # Utility method to check if substring from # low to high is palindrome or not. def isPalindrome ( string : str low : int high : int ) -> bool : while low < high : if string [ low ] != string [ high ]: return False low += 1 high -= 1 return True # This method returns -1 if it # is not possible to make string # a palindrome. It returns -2 if # string is already a palindrome. # Otherwise it returns index of # character whose removal can # make the whole string palindrome. def possiblepalinByRemovingOneChar ( string : str ) -> int : # Initialize low and right by # both the ends of the string low = 0 high = len ( string ) - 1 # loop until low and high cross each other while low < high : # If both characters are equal then # move both pointer towards end if string [ low ] == string [ high ]: low += 1 high -= 1 else : # If removing str[low] makes the whole string palindrome. # We basically check if substring str[low+1..high] is # palindrome or not. if isPalindrome ( string low + 1 high ): return low # If removing str[high] makes the whole string palindrome # We basically check if substring str[low+1..high] is # palindrome or not if isPalindrome ( string low high - 1 ): return high return - 1 # We reach here when complete string will be palindrome # if complete string is palindrome then return mid character return - 2 # Driver Code if __name__ == '__main__' : string = 'abecbea' idx = possiblepalinByRemovingOneChar ( string ) if idx == - 1 : print ( 'Not possible' ) else if idx == - 2 : print ( 'Possible without removing any character' ) else : print ( 'Possible by removing character at index' idx ) # This code is contributed by # sanjeev2552
C# // C# program to check whether // it is possible to make string // palindrome by removing one character using System ; class GFG { // Utility method to check if // substring from low to high is // palindrome or not. static bool isPalindrome ( string str int low int high ) { while ( low < high ) { if ( str [ low ] != str [ high ]) return false ; low ++ ; high -- ; } return true ; } // This method returns -1 if it is // not possible to make string a palindrome. // It returns -2 if string is already // a palindrome. Otherwise it returns // index of character whose removal can // make the whole string palindrome. static int possiblePalinByRemovingOneChar ( string str ) { // Initialize low and right // by both the ends of the string int low = 0 high = str . Length - 1 ; // loop until low and // high cross each other while ( low < high ) { // If both characters are equal then // move both pointer towards end if ( str [ low ] == str [ high ]) { low ++ ; high -- ; } else { /* * If removing str[low] makes the * whole string palindrome. We basically * check if substring str[low+1..high] * is palindrome or not. */ if ( isPalindrome ( str low + 1 high )) return low ; /* * If removing str[high] makes the whole string * palindrome. We basically check if substring * str[low+1..high] is palindrome or not. */ if ( isPalindrome ( str low high - 1 )) return high ; return - 1 ; } } // We reach here when complete string // will be palindrome if complete string // is palindrome then return mid character return - 2 ; } // Driver Code public static void Main ( String [] args ) { string str = 'abecbea' ; int idx = possiblePalinByRemovingOneChar ( str ); if ( idx == - 1 ) Console . Write ( 'Not Possible' ); else if ( idx == - 2 ) Console . Write ( 'Possible without ' + 'removing any character' ); else Console . Write ( 'Possible by removing' + ' character at index ' + idx ); } } // This code is contributed by shivanisinghss2110
JavaScript < script > // JavaScript program to check whether // it is possible to make string // palindrome by removing one character // Utility method to check if // substring from low to high is // palindrome or not. function isPalindrome ( str low high ) { while ( low < high ) { if ( str . charAt ( low ) != str . charAt ( high )) return false ; low ++ ; high -- ; } return true ; } // This method returns -1 if it is // not possible to make string a palindrome. // It returns -2 if string is already // a palindrome. Otherwise it returns // index of character whose removal can // make the whole string palindrome. function possiblePalinByRemovingOneChar ( str ) { // Initialize low and right // by both the ends of the string var low = 0 high = str . length - 1 ; // loop until low and // high cross each other while ( low < high ) { // If both characters are equal then // move both pointer towards end if ( str . charAt ( low ) == str . charAt ( high )) { low ++ ; high -- ; } else { /* * If removing str[low] makes the * whole string palindrome. We basically * check if substring str[low+1..high] * is palindrome or not. */ if ( isPalindrome ( str low + 1 high )) return low ; /* * If removing str[high] makes the whole string * palindrome. We basically check if substring * str[low+1..high] is palindrome or not. */ if ( isPalindrome ( str low high - 1 )) return high ; return - 1 ; } } // We reach here when complete string // will be palindrome if complete string // is palindrome then return mid character return - 2 ; } // Driver Code var str = 'abecbea' ; var idx = possiblePalinByRemovingOneChar ( str ); if ( idx == - 1 ) document . write ( 'Not Possible' ); else if ( idx == - 2 ) document . write ( 'Possible without ' + 'removing any character' ); else document . write ( 'Possible by removing' + ' character at index ' + idx ); // this code is contributed by shivanisinghss2110 < /script>
Вихід
Not Possible
Часова складність: O(N)
Просторова складність: O(1)
Створіть вікторину
