GroupAnagrams，变形词问题

问题描述：给定一个字符串数组，返回变形词组，变形词是指字母一样但顺序不一样的词。

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[

  ["ate", "eat","tea"],

  ["nat","tan"],

  ["bat"]

]

算法分析：可以用字符串本身字符进行排序，然后得到新的字符串，如果是变形词，那么排序后的字符串相同，可以把这相同的排序结果当做map的key，而把变形词当做map的value。

public class GroupAnagrams {

	public List<List<String>> groupAnagrams(String[] strs) {

        Map<String, List<String>> map = new HashMap<>();

        for(String str : strs)

        {

            char[] chr = str.toCharArray();

            Arrays.sort(chr);//对字符串排序

            String key = new String(chr);

            List<String> list = map.get(key);

            if(list == null)

            {

                list = new ArrayList<>();

            }

            list.add(str);

            map.put(key, list);

        }

        List<List<String>> list = new ArrayList<>();

        for(String key : map.keySet())

        {

            List<String> curr = map.get(key);

            Collections.sort(curr);//对list排序

            list.add(curr);

        }

        return list;

    }

}

巴特西

GroupAnagrams，变形词问题

最新文章

热门文章