lintcode，乱序字符串

给出一个字符串数组S，找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串，那么他存在一个字母集合相同，但顺序不同的字符串也在S中。 注意事项 所有的字符串都只包含小写字母 样例 对于字符串数组 [“lint”,”intl”,”inlt”,”code”] 返回 [“lint”,”inlt”,”intl”]

解题思路:设置hashmap来存储排序后的字符串与该字符串乱序的映射。

public class Solution { /** * @param strs: A list of strings * @return: A list of strings */ public List<String> anagrams(String[] strs) { List<String> rst = new ArrayList<String>(); if(strs == null || strs.length == 0) return rst; HashMap<String,ArrayList<String>> map = new HashMap<String,ArrayList<String>>(); for(int i = 0; i < strs.length; i++){ char[] arr = strs[i].toCharArray(); Arrays.sort(arr); String str = String.valueOf(arr); if(!map.containsKey(str)){ map.put(str,new ArrayList<String>()); } map.get(str).add(strs[i]); } for(ArrayList<String> str : map.values()){ if(str.size() > 1){ rst.addAll(str); } } return rst; } }

看了别人的思路稍微改了一下。map的键变成字符出现次数的字符串了。

public class Solution { /** * @param strs: A list of strings * @return: A list of strings */ public List<String> anagrams(String[] strs) { List<String> rst = new ArrayList<String>(); if(strs == null || strs.length == 0) return rst; HashMap<String,ArrayList<String>> map = new HashMap<String,ArrayList<String>>(); for(int i = 0; i < strs.length; i++){ /*char[] arr = strs[i].toCharArray(); Arrays.sort(arr); String str = String.valueOf(arr);*/ int[] arr = new int[26]; for(int j = 0; j < strs[i].length(); j++){ arr[strs[i].charAt(j)-'a']++; } String str = Arrays.toString(arr); if(!map.containsKey(str)){ map.put(str,new ArrayList<String>()); } map.get(str).add(strs[i]); } for(ArrayList<String> str : map.values()){ if(str.size() > 1){ rst.addAll(str); } } return rst; } }