Bazı küçük harfli alfabe karakterleri ve bir özel karakter nokta(.) içeren bir dize verilmiştir. Tüm noktaları bir alfabe karakteriyle değiştirmemiz gerekiyor, öyle ki sonuçta ortaya çıkan dizge bir palindrom haline geliyor, birçok olası değiştirme durumunda sözlükbilimsel olarak en küçük olan palindrom dizgesini seçmemiz gerekiyor. Tüm olası değiştirmelerden sonra dizeyi palindroma dönüştürmek mümkün değilse çıktı mümkün değildir.
Örnekler:
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
Bu sorunu şu şekilde çözebiliriz. Sonuçta elde edilen dizgenin palindrom olması gerektiğinden, başlangıçtaki nokta olmayan karakter çiftini kontrol edebiliriz, eğer eşleşmezlerse, o zaman doğrudan dönüş mümkün değildir çünkü yeni karakteri yalnızca noktaların konumuna yerleştirebiliriz, başka hiçbir yere koyamayız.
Bundan sonra, eğer mevcut karakter nokta ise, dizgenin karakterleri üzerinde yineleniriz, sonra eşleştirilmiş karakterini kontrol ederiz ((n – i -1)inci konumdaki karakter), eğer bu karakter de nokta ise, her iki karakteri de 'a' ile değiştirebiliriz çünkü 'a' en küçük küçük harfli alfabedir ve sonunda her ikisinin de başka bir karakterle değiştirilmesinin sözlükbilimsel olarak daha büyük palindromik dizgeyle sonuçlanacağını garanti eder. Diğer durumda, eşleştirilmiş karakter bir nokta değilse, o zaman palindrom dizisini oluşturmak için mevcut karakteri eşleştirilmiş karakteriyle değiştirmeliyiz.
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
Yukarıdaki prosedür bize sözlükbilimsel olarak en küçük palindrom dizisini verir.
Uygulama:
C++// C++ program to get lexicographically smallest // palindrome string #include
// 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 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# 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 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 ?> <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>
Çıkış
abcaeacba
Zaman karmaşıklığı: O(n) burada n dizenin uzunluğudur.
Yardımcı Uzay karmaşıklığı: O(1)