[抄题]:
给出一个字符串数组S,找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串,那么他存在一个字母集合相同,但顺序不同的字符串也在S中。
对于字符串数组 ["lint","intl","inlt","code"]
返回 ["lint","inlt","intl"]
[思维问题]:
[一句话思路]:
key是相同的哈希值(重要),value是不同的字符串 多余一个就取出来
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- result结果要放在ArrayList<String>中, 整体是arraylist,里面的东西是string。temp : map.values()表示把字符串里的东西都拿出来
- i < str.length() 字符串取长度要加括号
- 数据结构、返回语句都要写在自己的方法里,而不是solution class里
- 如果没有key,用put函数新建一个点加进去new ArrayList<String>(),这时候还没有添加字符串进去。之后不论有没有key,都要用add函数添加字符串:map.get(hash).add(str),所以不要写else。
-
int a = 378551;
int b = 63989;记住就好
[二刷]:
-
hash = nums[i] + hash * a;
用来生成hash值
a = a * b; - 字符串都存储于ArrayList<String>()动态数组之中,因为不知道会有多长
- str.charAt(i)表示取出字母
- int[] count数组在循环里定义,不要在循环外定义,免得有添加后删除不了的元素
[三刷]:
[四刷]:
[五刷]:
[总结]:
还是重要的作为key放在前面:这次是同一组合字母的hash值
[复杂度]:Time complexity: O(n) Space complexity: O(n)
[英文数据结构,为什么不用别的数据结构]:
key-value
[其他解法]:
[Follow Up]:
[题目变变变]:
public class Solution { /* * @param strs: A list of strings * @return: A list of strings */ //get hash private int getHash(int[] nums) { int hash = 0; int a = 378551; int b = 63989; for (int i = 0; i < nums.length; i++) { hash = nums[i] + hash * a; a = a * b; } return hash; } public List<String> anagrams(String[] strs) { HashMap<Integer,ArrayList<String>> map = new HashMap<Integer,ArrayList<String>>(); //put into count for (String str : strs) { int[] count = new int[26]; for (int i = 0; i < str.length(); i++) { count[str.charAt(i) - 'a']++; } int hash = getHash(count); //map or not if (!map.containsKey(hash)) { map.put(hash, new ArrayList<String>()); } map.get(hash).add(str); } //result ArrayList<String> result = new ArrayList<String>(); for (ArrayList<String> temp : map.values()) { if (temp.size() > 1) { result.addAll(temp); } } return result; } }