A palindrome is a word, phrase, or sequence that reads the same backwards and forwards. Given a palindrome write a program to print tge sorted list of all palindromes that can be constructed from the alphabeta of the given palindrome. All the palindromes should start in a newline. Input format: The firstline, an integer T , indicating the number of test cases T lines each containing one string (palindrome) Output form : Print sorted list of all palindromes constructed from the given palindrome of the ith tset case. If the entered string is not a palindrome, then it shiuld print as Not a plindrome. Sample Test Case : Sample input: 1 NITIN Sample Output: INTNI NITIN Explanation: There are only two palindromes that can be constructed from NITIN Me need code for this program .
Answers
Answer:
// i is the starting index and j is the ending index. i must be passed as 0 and j as n-1
minPalPartion(str, i, j) = 0 if i == j. // When string is of length 1.
minPalPartion(str, i, j) = 0 if str[i..j] is palindrome.
// If none of the above conditions is true, then minPalPartion(str, i, j) can be
// calculated recursively using the following formula.
minPalPartion(str, i, j) = Min { minPalPartion(str, i, k) + 1 +
minPalPartion(str, k+1, j) }
where k
Explanation:
import java.io.*;
class GFG {
public static int minCut(String a) {
int[] cut = new int[a.length()];
boolean[][] palindrome = new boolean[a.length()][a.length()];
for(int i = 0; i < a.length(); i++){
int minCut = i;
for(int j = 0; j <= i; j++){
if(a.charAt(i) == a.charAt(j) && (i - j < 2 || palindrome[j+1][i-1])){
palindrome[j][i] = true;
minCut = Math.min(minCut, j == 0 ? 0 :(cut[j-1] + 1));
}
}
cut[i] = minCut;
}
return cut[a.length() - 1];
}
public static void main (String[] args) {
System.out.println(minCut("aab"));
System.out.println(minCut("aabababaxx"));
}
}
Language used : Python Programming
Program :
from itertools import permutations
nt=int(input())
flag=0
while(flag!=nt):
st=""
st=str(input())
if st==st[::-1]:
update=[st]
st=list(st)
perm=permutations(st)
for i in perm:
check=''.join(i)
if check==check[::-1]:
if check not in update:
update.append(check)
print(check)
if len(update)==1:
print("Doesn't form any other palindrome")
else:
print("Not a palindrome")
flag=flag+1
Inputs and outputs :
Test case 1 : (opting for 1 test case)
Input :
1
NITIN
Output :
INTNI
Test case 2: (Opting for 4 test cases)
Input : (1)
4
NITIN
Output :
INTNI
Input : (2)
RACECAR
Output:
RCAEACR
ARCECRA
ACRERCA
CRAEARC
CARERAC
Input : (3)
BOB
Output :
Doesn't form any other palindrome
Input : (4)
HAPPY
Output :
Not a palindrome
Explanation :
- First take no.of test cases n as an input and write a while loop to run it for n times.
- Entering the loop ask user to enter a string.
- Check whether the string is palindrome or not. If yes, using permutations, take all the possibilities into a list variable. Else, print a statement stating that it isn't a palindrome.
- If it is a palindrome, form a list immediately and insert that palindrome into the string.
- Write a for loop that checks each probability by joining the substrings of a sub list that forms a word, whether it is palindrome or not.
- If the probable string is in list, ignore to print. Else, append the new string to the list and then print it.
- After all the probabilities of a string, are checked and the new palindromes are printed, initialize all the in loop things back to empty.
- If you find no other palindrome is happened by checking len(list)==1 (that 1 is of the original string), print a statement stating that.
- Update the flag variable by incrementing it to 1, and let the loop keep on running till that flag value equals to the no.of test cases entered. That's it!
Learn more :
- Advantages of Programming in python
brainly.in/question/11007952
- Indentation is must in python. Know more about it at :
brainly.in/question/17731168
