LeetCode-49

题目

结果

代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new LinkedList<>();
        for (String str : strs) {
            insert(ans, str);
        }
        return ans;
    }

    // 判断两个字符串是否为 '字母异位词'
    private boolean isSame(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        Arrays.sort(ch1);
        Arrays.sort(ch2);
        for (int i = 0; i < s1.length(); i++) {
            if (ch1[i] != ch2[i]) {
                return false;
            }
        }
        return true;
    }

    // 将s插入到ans合适的位置
    private void insert(List<List<String>> ans, String s) {
        boolean flag = false;
        for (List<String> list : ans) {
            if (isSame(list.get(0), s)) {
                list.add(s);
                flag = true;
                break;
            }
        }
        if (!flag) {
            List<String> list = new LinkedList<>();
            list.add(s);
            ans.add(list);
        }
    }
}

12月又写了一遍

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new LinkedList<>();
        for (String str : strs) {
            insert(ans, str);
        }
        return ans;
    }

    private void insert(List<List<String>> ans, String word) {
        boolean flag = false;
        for (var group : ans) {
            if (group.isEmpty()) {
                continue;
            }
            String head = group.get(0);
            if (anagram(head, word)) {
                flag = true;
                group.add(word);
                break;
            }
        }
        if (!flag) {
            ans.add(new LinkedList<>(List.of(word)));
        }
    }

    private boolean anagram(String word1, String word2) {
        if (word1.length() != word2.length()) {
            return false;
        }
        int[] count1 = new int[26];
        int[] count2 = new int[26];
        for (int i = 0; i < word1.length(); i++) {
            count1[word1.charAt(i) - 'a']++;
            count2[word2.charAt(i) - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (count1[i] != count2[i]) {
                return false;
            }
        }
        return true;
    }
}