哈希：字母异位词分组

问题描述

分组整理字符串数组中的异位词，同组的放一起，返回所有的分组。

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

说明：由相同字母组成的字符串，互为异位词。

求解思路：哈希

对字符串排序，互为异位词的字符串排序之后一定相同。从这个角度出发，就可以把排序之后的字符串作为key，异位词作为value。以上示例处理成这样：

class Solution {public List<List<String>> groupAnagrams(String[] strs) {HashMap<String, List<String>> hashMap = new HashMap<>();for (String s : strs) {// 先将字符串转为字符数组，然后对是字符数组进行排序char[] charArr = s.toCharArray();Arrays.sort(charArr);// 通过new String的构造方式，使用char数组构造字符串String strKey = new String(charArr);// 使用getOrDefault方法，处理value为空的情况List<String> list = hashMap.getOrDefault(strKey, new ArrayList<>());list.add(s);hashMap.put(strKey, list);}// 构造返回参数// 方法一：遍历hashMap// List<List<String>> result = new ArrayList<List<String>>();// for(Map.Entry<String,List<String>> entry : hashMap.entrySet()){//     result.add(entry.getValue());// }// return result;// 方法二：直接调用hashMap的values()方法return new ArrayList<List<String>>(hashMap.values());}
}

常用操作回顾

1、遍历hashMap的六种方法

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;public class PrintMap {public static void main(String[] args) {HashMap<String, Integer> map = new HashMap<>();map.put("Lucy", 18);map.put("Jack", 20);map.put("Layla", 22);// 方法一：通过entrySet()方法for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println("key:" + entry.getKey() + ",value:" + entry.getValue());}// 方式二：使用values方法；只能访问值for (Integer value : map.values()) {System.out.println("value" + value);}// 方式三：使用keySet方法；只能访问键for (String key : map.keySet()) {System.out.println("key:" + key);}// 方式四：使用forEach()；java8以上map.forEach((key, value) -> System.out.println("key:" + key + ",value:" + value));// 方式五：使用迭代器Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();while (iterator.hasNext()) {Map.Entry<String, Integer> entry = iterator.next();System.out.println("key:" + entry.getKey() + ",value:" + entry.getValue());}// 方式六：使用java Stream API；Java8以上map.entrySet().stream().forEach(entry -> System.out.println("key:" + entry.getKey() + ",value:" + entry.getValue()));}
}

2、构造字符串的七种方法

String str = "Hello, World!";

String str = new String("Hello, World!");

String name = "World";
String greeting = String.format("Hello, %s!", name); // 输出: Hello, World!

String firstName = "John";
String lastName = "Doe";
String fullName = firstName + " " + lastName; 
// 输出: John Doe

StringBuilder sb = new StringBuilder();
sb.append("Hello, ");
sb.append("World!");
String result = sb.toString(); 
// 输出: Hello, World!

String[] parts = {"Hello", "World"};
String message = String.join(", ", parts); 
// 输出: Hello, World

int number = 123;
String numberStr = String.valueOf(number); // 输出: "123"

3、字符串数组的四种排序

方法一：数组使用Arrays.sort()

import java.util.Arrays;public class Main {public static void main(String[] args) {String[] strings = {"banana", "apple", "orange", "mango"};Arrays.sort(strings);System.out.println(Arrays.toString(strings));}
}

方法二：List使用Collections.sort()（对于List<String>）

import java.util.Arrays;
import java.util.Collections;
import java.util.List;public class Main {public static void main(String[] args) {List<String> strings = Arrays.asList("banana", "apple", "orange", "mango");Collections.sort(strings);System.out.println(strings);}
}

方法三：使用自定义比较器

例如：按字符串长度排序

import java.util.Arrays;
import java.util.Comparator;public class Main {public static void main(String[] args) {String[] strings = {"banana", "apple", "orange", "mango"};Arrays.sort(strings, new Comparator<String>() {@Overridepublic int compare(String s1, String s2) {return Integer.compare(s1.length(), s2.length()); // 按字符串长度排序}});System.out.println(Arrays.toString(strings)); // 按长度排序后的数组}
}

Lambda表达式简化:

Arrays.sort(strings, (s1, s2) -> Integer.compare(s1.length(), s2.length()));

方法四：利用Stream API进行排序

import java.util.Arrays;
import java.util.stream.Collectors;public class Main {public static void main(String[] args) {String[] strings = {"banana", "apple", "orange", "mango"};String[] sortedStrings = Arrays.stream(strings).sorted() // 默认按字典顺序排序字符串数组元素.toArray(String[]::new); // 收集回数组中System.out.println(Arrays.toString(sortedStrings)); // 输出排序后的数组内容}
}