我需要一个非强力算法来确定你需要从一个单词中删除的最小字母数量,以便它成为回文的一个字谜。
例如:abba
- > 0,abbac
- > 0,aabbfghj
- > 3,a
- > 0,abcdefghij
- > 9。
蛮力算法看起来像这样:
1. Send word to method (2.) with counter 0
2. Check if any anagrams of word is palindrome, if yes return counter, if no go to 3.
3. Remove head of word, send to method (2.) with counter++
蛮力方法是O(n * n!)复杂性我相信(因为对于每个单词,都有n!anagrams,n个字母要删除)。例如,对于字符串n = 1000,这将花费太长时间。所以我需要一个更好的算法,但我不确定我可以检查字符串以确定删除所需的字母数量。
因为n> 1的所有回文都有一对/字母多数(aba
有对aa
,abcba
对aa
和bb
,aaab
有aaa
)我想要删除一个字母的所有倍数然后返回新单词-1的长度,或只是长度,如果它是0.这适用于很多单词,但它仍然失败了一些。例如:
"aabbfghj" (remove pairs) -> "fghj" (length >0) -> return length-1 = 3 correct
"aabbcc" -> "" (!length >0) -> return length = 0 correct
"aaabb" -> "" -> 0 correct
"aaabbb" -> "" -> 0 correct
"aaabbbccdef" -> "def" -> 2 correct
"aaaaab" -> "b" -> 0 correct
"aabbc" -> "c" -> 0 correct
"aaabbc" -> "c" -> 0 incorrect (should be 1)
我错过了一些非常简单的东西吗?如何构建一个算法,该算法将返回您需要从单词中删除的最少量的字母以获得回文的angram?
我错过了一些非常简单的东西吗?
是的,你是 :-)
作为回文的字谜可以表征如下:
一个词w
是一个回文的字谜,当且仅当有,最多存在一个字符c
,使得c
中w
的出现次数是奇数(我告诉你为什么这是真的,测试简单的情况)。
因此,给出一个单词w
,计算w
的每个字符,它出现的次数。然后计算在w
中有多少个字符出现奇数次(让我们称之为k
)。要删除的字母数量w
可以是回文的字谜是0
,如果k=0
或k=1
。否则它是k-1
。