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