Data Structure Questions and Answers-Minimum Insertions to form a Palindrome
Click on any option to know the CORRECT ANSWERS
Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?
Both recursion and dynamic programming
Question 1 Explanation:
Dynamic programming and recursion can be used to solve the problem.
In which of the following cases will the number of insertions to form a palindrome be minimum?
String of length one
String with all same characters
All of the mentioned
Question 2 Explanation:
In all the mentioned cases, the number of insertions will be zero since the strings are already palindromes.
In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string.
Question 3 Explanation:
In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to length of the string minus one. For example, consider the string "abc". The string can be converted to "abcba" by inserting "a" and "b". The number of insertions is two, which is equal to length minus one.
Consider the string "efge". What is the minimum number of insertions required to make the string a palindrome?
Question 4 Explanation:
The string can be converted to "efgfe" by inserting "f" or to "egfge" by inserting "g". Thus, only one insertion is required.
Consider the string "abbccbba". What is the minimum number of insertions required to make the string a palindrome?
Question 5 Explanation:
The given string is already a palindrome. So, no insertions are required.
There are 5 questions to complete.