Anagrams
发布时间：2020-12-13 20:12:38 所属栏目：PHP教程 来源：网络整理
导读：本文是在学习中的总结，欢迎转载但请注明出处：http://blog.csdn.net/pistolove/article/details/42744709 Given an array of strings,return all groups of strings that are anagrams. Note: All inputs will be in lower-case. 思路： （1）如果不知道ana
|
本文是在学习中的总结，欢迎转载但请注明出处：http://blog.csdn.net/pistolove/article/details/42744709
Given an array of strings,return all groups of strings that are anagrams. Note: All inputs will be in lower-case.
思路： （1）如果不知道anagrams的意思，很容易将题意理解错了。最开始我理解的意思是求给定字符串数组的全排列有多少种。OJ几次都错了，后来被迫查了下anagrams的意思才知道，anagrams：由颠倒字母顺序而构成的字[短语]。看来英语还是要学好啊。该题意为给定1个字符串数组，求得该数组中所有由相同字符组成的字符串序列。例如：给定字符串数组["abc","acb","cab","xyz","fg"]，则结果为["abc","cab"]。 （2）本文主要应用Map来存储，其中Key为经过排序后的字符串（通过对字符串进行排序，能够将顺序打乱的字符串变得相同），value为打乱顺序的1系列字符串。上例中key为"abc"，value为["abc","cab"]。然后通过判断Map中value对应List中元素个数是不是大于1，如果大于1，说明有多个由相同字符组成但是顺序被打乱的字符串。 （3）详见下方代码。希望对你有所帮助。（PS：其中Arrays.sort()方法是对给定的数组进行排序）
算法代码实现以下： /**
*
* @author liqq
*/
public static List<String> anagrams(String[] strs) {
if (strs == null || strs.length < 2)
return new ArrayList<String>();
Map<String,List<String>> maps = new HashMap<String,List<String>>();
for (String str : strs) {
char[] arr = str.toCharArray();
Arrays.sort(arr);
String key = new String(arr);
if (!maps.containsKey(key)) {
maps.put(key,new ArrayList<String>());
}
List<String> list = maps.get(key);
list.add(new String(str));
}
List<String> result = new ArrayList<String>();
for (Iterator<String> iterator = maps.keySet().iterator(); iterator
.hasNext();) {
String key = iterator.next();
if (maps.get(key).size() > 1) {
result.addAll(maps.get(key));
}
}
return result;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |