Permutation-Palindrome Leetcode
Write an efficient function that checks whether any permutation ↴ of an input string is a palindrome ↴ .
Examples:
"civic" should return True
"ivicc" should return True
"civil" should return False
"livci" should return False
又是Leetcode上一个付费题目。 看似需要了解如何求permutation和palindrome,其实完全不用。
1.当然啦,最基本方法是对String求出所有的permutation,可以用递归实现,在求出每个permutation的最后,对其验证是否为palindrome(双指针一前一后检查)。
2.第一个方法肯定没错,但是效率肯定很低啦,这题其实只需要返回是否含有1个palindrome的可能,因此用hashset足够了。
HashSet基本思路也就是从左向右扫一遍,如果元素不存在set中,放入。如果存在,拿出来删掉。因为palindrome都是对称的,表示所有元素都是成对出现的(偶数情况,奇数情况下可以有一个元素在正中心),因此在遍历完一遍后,如果Hashset 内有超过1个以上的元素,则不为palindrome,反之则是palindrome。
No comments:
Post a Comment