置換後の最小回文
いくつかの小文字のアルファベット文字と 1 つの特殊文字ドット (.) を含む文字列を指定します。可能な置換が多数ある場合には、辞書編集上最小の回文文字列を選択する必要があるため、結果の文字列が回文になるように、すべてのドットを何らかのアルファベット文字に置き換える必要があります。可能な置換をすべて行っても文字列を回文に変換できない場合は、「不可能」と出力されます。
例:
Input : str = ab..e.c.a Output : abcaeacba The smallest palindrome which can be made after replacement is 'abcaeacba' We replaced first dot with 'c' second dot with 'a' third dot with 'a' and fourth dot with 'b' Input : str = ab..e.c.b Output : Not Possible It is not possible to convert above string into palindrome
この問題は次のように解決できます。結果の文字列は回文である必要があるため、開始時にドット以外の文字のペアをチェックできます。それらが一致しない場合は、他の場所ではなくドットの位置にのみ新しい文字を配置できるため、直接返すことはできません。
その後、文字列の文字を反復処理します。現在の文字がドットの場合は、そのペアの文字 ((n – i -1) 番目の位置の文字) を確認します。その文字もドットであれば、両方の文字を「a」に置き換えることができます。「a」は最小の小文字アルファベットであり、最後に最小の辞書編集文字列が保証されます。両方を他の文字に置き換えると、辞書編集的により大きな回文文字列になります。他の場合、ペアの文字がドットでない場合、文字列回文を作成するには、現在の文字をそのペアの文字で置き換える必要があります。
So in short If both 'i' and 'n- i- 1' are dot replace them by ‘a’ If one of them is a dot character replace that by other non-dot character
上記の手順により、辞書編集上最小の回文文字列が得られます。
実装：
C++ // C++ program to get lexicographically smallest // palindrome string #include using namespace std ; // Utility method to check str is possible palindrome // after ignoring . bool isPossiblePalindrome ( string str ) { int n = str . length (); for ( int i = 0 ; i < n / 2 ; i ++ ) { /* If both left and right character are not dot and they are not equal also then it is not possible to make this string a palindrome */ if ( str [ i ] != '.' && str [ n - i -1 ] != '.' && str [ i ] != str [ n - i -1 ]) return false ; } return true ; } // Returns lexicographically smallest palindrom // string if possible string smallestPalindrome ( string str ) { if ( ! isPossiblePalindrome ( str )) return 'Not Possible' ; int n = str . length (); // loop through character of string for ( int i = 0 ; i < n ; i ++ ) { if ( str [ i ] == '.' ) { // if one of character is dot replace dot // with other character if ( str [ n - i - 1 ] != '.' ) str [ i ] = str [ n - i - 1 ]; // if both character are dot then replace // them with smallest character 'a' else str [ i ] = str [ n - i - 1 ] = 'a' ; } } // return the result return str ; } // Driver code to test above methods int main () { string str = 'ab..e.c.a' ; cout < < smallestPalindrome ( str ) < < endl ; return 0 ; }
Java // Java program to get lexicographically // smallest palindrome string class GFG { // Utility method to check str is // possible palindrome after ignoring static boolean isPossiblePalindrome ( char str [] ) { int n = str . length ; for ( int i = 0 ; i < n / 2 ; i ++ ) { /* If both left and right character are not dot and they are not equal also then it is not possible to make this string a palindrome */ if ( str [ i ] != '.' && str [ n - i - 1 ] != '.' && str [ i ] != str [ n - i - 1 ] ) return false ; } return true ; } // Returns lexicographically smallest // palindrome string if possible static void smallestPalindrome ( char str [] ) { if ( ! isPossiblePalindrome ( str )) System . out . println ( 'Not Possible' ); int n = str . length ; // loop through character of string for ( int i = 0 ; i < n ; i ++ ) { if ( str [ i ] == '.' ) { // if one of character is dot // replace dot with other character if ( str [ n - i - 1 ] != '.' ) str [ i ] = str [ n - i - 1 ] ; // if both character are dot // then replace them with // smallest character 'a' else str [ i ] = str [ n - i - 1 ] = 'a' ; } } // return the result for ( int i = 0 ; i < n ; i ++ ) System . out . print ( str [ i ] + '' ); } // Driver code public static void main ( String [] args ) { String str = 'ab..e.c.a' ; char [] s = str . toCharArray (); smallestPalindrome ( s ); } } // This code is contributed // by ChitraNayal
Python 3 # Python 3 program to get lexicographically # smallest palindrome string # Utility method to check str is # possible palindrome after ignoring def isPossiblePalindrome ( str ): n = len ( str ) for i in range ( n // 2 ): # If both left and right character # are not dot and they are not # equal also then it is not possible # to make this string a palindrome if ( str [ i ] != '.' and str [ n - i - 1 ] != '.' and str [ i ] != str [ n - i - 1 ]): return False return True # Returns lexicographically smallest # palindrome string if possible def smallestPalindrome ( str ): if ( not isPossiblePalindrome ( str )): return 'Not Possible' n = len ( str ) str = list ( str ) # loop through character of string for i in range ( n ): if ( str [ i ] == '.' ): # if one of character is dot # replace dot with other character if ( str [ n - i - 1 ] != '.' ): str [ i ] = str [ n - i - 1 ] # if both character are dot # then replace them with # smallest character 'a' else : str [ i ] = str [ n - i - 1 ] = 'a' # return the result return str # Driver code if __name__ == '__main__' : str = 'ab..e.c.a' print ( '' . join ( smallestPalindrome ( str ))) # This code is contributed by ChitraNayal
C# // C# program to get lexicographically // smallest palindrome string using System ; public class GFG { // Utility method to check str is // possible palindrome after ignoring static bool isPossiblePalindrome ( char [] str ) { int n = str . Length ; for ( int i = 0 ; i < n / 2 ; i ++ ) { /* If both left and right character are not dot and they are not equal also then it is not possible to make this string a palindrome */ if ( str [ i ] != '.' && str [ n - i - 1 ] != '.' && str [ i ] != str [ n - i - 1 ]) return false ; } return true ; } // Returns lexicographically smallest // palindrome string if possible static void smallestPalindrome ( char [] str ) { if ( ! isPossiblePalindrome ( str )) Console . WriteLine ( 'Not Possible' ); int n = str . Length ; // loop through character of string for ( int i = 0 ; i < n ; i ++ ) { if ( str [ i ] == '.' ) { // if one of character is dot // replace dot with other character if ( str [ n - i - 1 ] != '.' ) str [ i ] = str [ n - i - 1 ]; // if both character are dot // then replace them with // smallest character 'a' else str [ i ] = str [ n - i - 1 ] = 'a' ; } } // return the result for ( int i = 0 ; i < n ; i ++ ) Console . Write ( str [ i ] + '' ); } // Driver code public static void Main () { String str = 'ab..e.c.a' ; char [] s = str . ToCharArray (); smallestPalindrome ( s ); } } // This code is contributed by PrinciRaj1992
PHP // PHP program to get lexicographically // smallest palindrome string // Utility method to check str is // possible palindrome after ignoring function isPossiblePalindrome ( $str ) { $n = strlen ( $str ); for ( $i = 0 ; $i < $n / 2 ; $i ++ ) { /* If both left and right character are not dot and they are not equal also then it is not possible to make this string a palindrome */ if ( $str [ $i ] != '.' && $str [ $n - $i - 1 ] != '.' && $str [ $i ] != $str [ $n - $i - 1 ]) return false ; } return true ; } // Returns lexicographically smallest // palindrome string if possible function smallestPalindrome ( $str ) { if ( ! isPossiblePalindrome ( $str )) return 'Not Possible' ; $n = strlen ( $str ); // loop through character of string for ( $i = 0 ; $i < $n ; $i ++ ) { if ( $str [ $i ] == '.' ) { // if one of character is dot // replace dot with other character if ( $str [ $n - $i - 1 ] != '.' ) $str [ $i ] = $str [ $n - $i - 1 ]; // if both character are dot // then replace them with // smallest character 'a' else $str [ $i ] = $str [ $n - $i - 1 ] = 'a' ; } } // return the result return $str ; } // Driver code $str = 'ab..e.c.a' ; echo smallestPalindrome ( $str ); // This code is contributed // by ChitraNayal ?>
JavaScript < script > // Javascript program to get lexicographically // smallest palindrome string // Utility method to check str is // possible palindrome after ignoring function isPossiblePalindrome ( str ) { let n = str . length ; for ( let i = 0 ; i < Math . floor ( n / 2 ); i ++ ) { /* If both left and right character are not dot and they are not equal also then it is not possible to make this string a palindrome */ if ( str [ i ] != '.' && str [ n - i - 1 ] != '.' && str [ i ] != str [ n - i - 1 ]) return false ; } return true ; } // Returns lexicographically smallest // palindrome string if possible function smallestPalindrome ( str ) { if ( ! isPossiblePalindrome ( str )) document . write ( 'Not Possible' ); let n = str . length ; // loop through character of string for ( let i = 0 ; i < n ; i ++ ) { if ( str [ i ] == '.' ) { // if one of character is dot // replace dot with other character if ( str [ n - i - 1 ] != '.' ) str [ i ] = str [ n - i - 1 ]; // if both character are dot // then replace them with // smallest character 'a' else str [ i ] = str [ n - i - 1 ] = 'a' ; } } // return the result for ( let i = 0 ; i < n ; i ++ ) document . write ( str [ i ] + '' ); } // Driver code let str = 'ab..e.c.a' ; let s = str . split ( '' ); smallestPalindrome ( s ); // This code is contributed by rag2127 < /script>
出力
abcaeacba
時間計算量: O(n) ここで、n は文字列の長さです。
補助スペースの複雑さ: O(1)
