leetcode49字母异位词分组
思路一
知道要用hash,但是当时不知道怎么解决字符串的全排列。一个单词可以变成好多单词,我怎么对这些单词枚举呢。结果发现可以sort,那么字母一样的单词一定一样,然后将单词放到hashmap里面,凡是排完序一样的单词都放到一个队列里去。
代码一
class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String str:strs){String s1 = sortString(str);if (map.containsKey(s1)){map.get(s1).add(str);}else {List<String> list = new ArrayList<>();list.add(str);map.put(s1, list);}}List<List<String>> result = new ArrayList<>();for (Map.Entry<String, List<String>> entry : map.entrySet()){result.add(entry.getValue());}return result;}private String sortString(String str) {char[] chars = str.toCharArray();Arrays.sort(chars);return String.valueOf(chars);}}
思路二
class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String str:strs){String s1 = stringToKey(str);if (map.containsKey(s1)){map.get(s1).add(str);}else {List<String> list = new ArrayList<>();list.add(str);map.put(s1, list);}}List<List<String>> result = new ArrayList<>();for (Map.Entry<String, List<String>> entry : map.entrySet()){result.add(entry.getValue());}return result;}private String stringToKey(String str) {char[] chars = str.toCharArray();int[] z = new int[26];for (char ch : chars){z[ch-97] ++;}StringBuilder stringBuilder = new StringBuilder();for (int i = 0; i < 26; i++) {if (z[i] != 0){stringBuilder.append((char)(i+97));stringBuilder.append(z[i]);}}return stringBuilder.toString();}}
就是构建key
stringToKey就是想法构建一个key,如何把 abc acb cba 映射为相同的key,就是字母和出现的次数