Odstráňte znak z reťazca, aby sa z neho stal palindróm
Pri danom reťazci musíme skontrolovať, či je možné z tohto reťazca urobiť palindróm po odstránení práve jedného znaku z neho.
Príklady:
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
Tento problém môžeme vyriešiť nájdením pozície nesúladu. V reťazci začneme cyklovať tak, že na oboch koncoch ponecháme dva ukazovatele, ktoré sa po každej iterácii pohybujú smerom k strednej polohe, táto iterácia sa zastaví, keď nájdeme nesúlad, pretože je povolené odstrániť iba jeden znak, tu máme dve možnosti
Pri nezhode buď odstráňte znak označený ľavým ukazovateľom alebo odstráňte znak označený pravým ukazovateľom.
Skontrolujeme oba prípady, ktoré si pamätáme, pretože sme prešli rovnaký počet krokov z oboch strán, tento stredný reťazec by mal byť tiež palindróm po odstránení jedného znaku, takže skontrolujeme dva podreťazce jeden odstránením ľavého znaku a jeden odstránením pravého znaku a ak jeden z nich je palindróm, potom môžeme vytvoriť úplný reťazcový palindróm odstránením zodpovedajúceho znaku a ak oba podreťazce nie sú pod daným reťazcom, nie je možné urobiť palindróm úplný.
Implementácia:
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>
Výstup
Not Possible
Časová zložitosť: O(N)
Priestorová zložitosť: O(1)
Vytvoriť kvíz
