版權(quán)聲明:本文為博主原創(chuàng)文章悴势,未經(jīng)博主允許不得轉(zhuǎn)載蹭劈。
難度:中等
要求:
給出一個(gè)字符串?dāng)?shù)組S酿傍,找到其中所有的亂序字符串(Anagram)。如果一個(gè)字符串是亂序字符串踪区,那么他存在一個(gè)字母集合相同昆烁,但順序不同的字符串也在S中。
注意事項(xiàng)
所有的字符串都只包含小寫字母
樣例
對于字符串?dāng)?shù)組 ["lint","intl","inlt","code"]
返回 ["lint","inlt","intl"]
思路:
public class Solution {
/**
* @param strs: A list of strings
* @return: A list of strings
*/
public List<String> anagrams(String[] strs) {
if (strs == null || strs.length == 0) {
return null;
}
List<String> reValue = new ArrayList<String>();
Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
for (String s : strs) {
String key = getKey(s);
if (map.containsKey(key)) {
map.get(key).add(s);
} else {
ArrayList<String> list = new ArrayList<String>();
list.add(s);
map.put(key, list);
}
}
for (ArrayList<String> list : map.values()) {
if (list.size() > 1) {
reValue.addAll(list);
}
}
return reValue;
}
/**
* 生成key(比如 "and" 和 "dan"缎岗,他們的“ Hash 值 ”就是“a1d1n1"静尼,"array" 和 "yarar" 就是 a2r2y1)
*
* @param s
* @return
*/
private String getKey(String s) {
if (s == null || s.length() == 0) {
return "";
}
int[] count = new int['z' - 'a' + 1];
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
count[c - 'a']++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < count.length; i++) {
int value = count[i];
if (value > 0) {
sb.append(i + 'a').append(value);
}
}
return sb.toString();
}
}