Problem
Given a string, determine if a permutation of the string could form a palindrome.
Example 1:
Input: "code"
Output: false
Example 2:
Input: "aab"
Output: true
Example 3:
Input: "carerac"
Output: true
Soultion
Analysis
If a string can form a palindrome, it should contain characters with even number of occurences and one character with odd number of occurences , or only characters with even number of occurences.
We can use set to record the characters with odd number of occurences. Traverse the given string s
, if we meet a character odd number of times, put it in the set, otherwise remove it. Return whether the number of characters in the set is 0 or 1.
Python implementation
|
|
Java implementation
|
|
Time complexity
O(n). n is length of string s
, as we traverse each character in it.
Space complexity
O(1). For worst case, the set has all unique letters, total number of which is fixed.
Link
266. Palindrome Permutation
(中文版)
近期评论