Sunday, August 7, 2016

266. Palindrome Permutation

I was thinking to traverse the buckets twice. First round is to count the number of each character. The second round is to count the number of odds. If odds is less than 2, return true. Otherwise, return false.
The top rated solution combine the two rounds into one round but actually the same running time.

1:  class Solution {  
2:  public:  
3:    bool canPermutePalindrome(string s) {  
4:      vector<int> chars(256, 0);  
5:      int odd = 0;  
6:      for (char c : s) {  
7:        odd += ++chars[c] & 1 ? 1 : -1;  
8:      }  
9:      return odd < 2;  
10:    }  
11:  };  

No comments:

Post a Comment