CC--Q1.4

1.4 Palindrome Permutation: Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rea rrangement of letters. The palindrome does not need to be limited to just dictionary words.
EXAMPLE
Input: Tact Coa
Output: True (permutations: "taco cat". "atco cta". etc.)

Just check that no more than one character appears an odd number of times. Because if there is one, then it must be in the middle of the palindrome. So we can't have two of them.

For even Palindrome, all char number must be even
For odd palindrome, all char number must be even except one odd.

public boolean canPermutePalindrome(String s) {
        Set<Character> set=new HashSet<Character>();
        for(int i=0; i<s.length(); i++){
            if (!set.contains(s.charAt(i)))
                set.add(s.charAt(i));
            else 
                set.remove(s.charAt(i));
        }
        return set.size()==0 || set.size()==1;
    }

Or reduce the space usage by using a bit vector

public boolean canPermutePalindrome(String s) {
    BitSet bs = new BitSet();
    for (byte b : s.getBytes())
        bs.flip(b);
    return bs.cardinality() < 2;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,776评论 0 33
  • 最近我刚刚看完了一本书,是美国作家埃克哈特·托利的灵性书籍《当下的力量》。这本书由《遇见未知的自己》的作者,同是灵...
    毛球女神进化馆阅读 1,718评论 3 6
  • 很喜欢在夜深人静的时候,独自放上一曲缓缓的歌——陶醉、享受!此刻,正循环播放着史逸欣的《绿岛小夜曲》。 想写下点什...
    不听话阅读 561评论 0 1
  • 每天又忙又累!但是没有充实感,甚至迷茫于为何奔波!有时突然梦醒却有不知身在何处的感觉!
    花样儿阅读 134评论 0 0