与えられた文字列からちょうど 1 文字を削除した後、この文字列を回文にすることが可能かどうかを確認する必要があります。
例:
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
この問題は、不一致の位置を見つけることで解決できます。各反復後に中央位置に向かって移動する 2 つのポインターを両端に保持することで文字列のループを開始します。削除できるのは 1 文字だけであるため、この反復は不一致が見つかったときに停止します。ここでは 2 つの選択肢があります。
不一致の場合は、左ポインタが指す文字を削除するか、右ポインタが指す文字を削除します。
両側から同じ数のステップをたどったので、両方のケースを確認します。1 文字を削除すると、この中間の文字列も回文になるはずです。そのため、2 つの部分文字列を 1 つは左側の文字を削除し、もう 1 つは右側の文字を削除して確認します。そのうちの 1 つが回文である場合は、対応する文字を削除することで完全な文字列回文を作成できます。両方の部分文字列が回文でない場合は、指定された制約の下で完全な文字列を回文にすることはできません。
実装：
C++// C/C++ program to check whether it is possible to make // string palindrome by removing one character #include
// 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
# 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# 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
<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)
クイズの作成