資訊專欄INFORMATION COLUMN
摘要：最笨的方法就是用的解法，找出所有的，然后再用中判斷回文的方法來判斷結(jié)果中是否有回文。而中心對稱點(diǎn)如果是字符，該字符會是奇數(shù)次，如果在兩個(gè)字符之間，則所有字符都是出現(xiàn)偶數(shù)次。
Palindrome Permutation
哈希表法 復(fù)雜度Given a string, determine if a permutation of the string could form a palindrome.
For example, "code" -> False, "aab" -> True, "carerac" -> True.
Hint:
Consider the palindromes of odd vs even length. What difference do you notice? Count the frequency of each character. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?
時(shí)間 O(N) 空間 O(N)
思路Leetcode的提示其實(shí)已經(jīng)將答案告訴我們了。最笨的方法就是用Permutations的解法，找出所有的Permutation，然后再用Palindrome中判斷回文的方法來判斷結(jié)果中是否有回文。但是我們考察一下回文的性質(zhì)，回文中除了中心對稱點(diǎn)的字符，其他字符都會出現(xiàn)偶數(shù)次。而中心對稱點(diǎn)如果是字符，該字符會是奇數(shù)次，如果在兩個(gè)字符之間，則所有字符都是出現(xiàn)偶數(shù)次。所以，我們只要判斷下字符串中每個(gè)字符出現(xiàn)的次數(shù)，就知道該字符串的其他排列方式中是否有回文了。
注意本題也可以用一個(gè)HashSet，第偶數(shù)個(gè)字符可以抵消Set中的字符，最后判斷Set的大小是否小于等于1就行了。
代碼HashMap實(shí)現(xiàn)
public class Solution {
public boolean canPermutePalindrome(String s) {
Map map = new HashMap();
// 統(tǒng)計(jì)每個(gè)字符的個(gè)數(shù)
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
Integer cnt = map.get(c);
if(cnt == null){
cnt = new Integer(0);
}
map.put(c, ++cnt);
}
// 判斷是否只有不大于一個(gè)的奇數(shù)次字符
boolean hasOdd = false;
for(Character c : map.keySet()){
if(map.get(c) % 2 == 1){
if(!hasOdd){
hasOdd = true;
} else {
return false;
}
}
}
return true;
}
}
HashSet實(shí)現(xiàn)
public class Solution {
public boolean canPermutePalindrome(String s) {
Set set = new HashSet();
for(int i = 0; i < s.length(); i++){
// 出現(xiàn)的第偶數(shù)次，將其從Set中移出
if(set.contains(s.charAt(i))){
set.remove(s.charAt(i));
} else {
// 出現(xiàn)的第奇數(shù)次，將其加入Set中
set.add(s.charAt(i));
}
}
// 最多只能有一個(gè)奇數(shù)次字符
return set.size() <= 1;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64591.html
摘要：有效三角形的個(gè)數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字。總結(jié)本題和三數(shù)之和很像，都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來解決這個(gè)問題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...
Problem Given a string, determine if a permutation of the string could form a palindrome. Example 1: Input: codeOutput: falseExample 2: Input: aabOutput: trueExample 3: Input: careracOutput: true Solu...
Problem Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form. Example Given s = aabb, return [abba,baa...
摘要：反轉(zhuǎn)比較法復(fù)雜度時(shí)間空間思路回文數(shù)有一個(gè)特性，就是它反轉(zhuǎn)后值是一樣的。代碼逐位比較法復(fù)雜度時(shí)間空間思路反轉(zhuǎn)比較有可能會溢出，但我們遍歷每一位的時(shí)候其實(shí)并不用保存上一位的信息，只要和當(dāng)前對應(yīng)位相等就行了。首先，負(fù)數(shù)是否算回文。 Palindrome Number Determine whether an integer is a palindrome. Do this witho...
摘要：描述給定一組唯一的單詞，找出所有不同的索引對，使得列表中的兩個(gè)單詞，，可拼接成回文串。遍歷每一個(gè)單詞，對每一個(gè)單詞進(jìn)行切片，組成和。 Description Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenatio...
閱讀 3730·2021-11-11 10:58
閱讀 2524·2021-09-22 15:43
閱讀 2895·2019-08-30 15:44
閱讀 2224·2019-08-30 13:08
閱讀 1854·2019-08-29 17:28
閱讀 913·2019-08-29 10:54
閱讀 702·2019-08-26 11:46
閱讀 3531·2019-08-26 11:43
