Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- compute the minimum number of removals in order to make the string palindrome
- '''
- def palindromic_substring(word):
- dp = [[-1 for _ in range(len(word) + 1)] for _ in range(len(word)+1)]
- def count_nr_chars(word, i, j, count):
- if dp[i][j] != -1:
- return dp[i][j]
- if i >= j:
- return count
- if word[i] == word[j]:
- value = count_nr_chars(word, i + 1, j - 1, count)
- else:
- value = min(count_nr_chars(word, i + 1, j, count + 1),
- count_nr_chars(word, i, j - 1, count + 1),
- count_nr_chars(word, i + 1, j - 1, count + 2))
- dp[i][j] = value
- return dp[i][j]
- return count_nr_chars(word, 0, len(word) - 1, 0)
- print(palindromic_substring('zmlbc'))
Add Comment
Please, Sign In to add comment