异位构词游戏 - litonghui/TechBlog GitHub Wiki

异位构词游戏

指一个词或短句的字母重新排列顺序，原文中所有字母的每次出现都被被使用一次，这样构造出另外一些新的词或短句。如何去判断两个词是否异位？

思路一：首先判断两个字符串s和t长度是否相同，不相同直接返回false，否则遍历字符串s中的每一个字符，在t字符串中查找，如果有相同的替换为特殊字符'#',直到s最后一个字符。查看t字符串如果每一个位置都被'#'代替，则为异位构词否则不是。

public boolean isAnagram(String s, String t) {
    boolean isAnagram = true;
    if (s.length() != t.length())
        return false;
    char [] sc = s.toCharArray();
    char [] st = t.toCharArray();
    for (int i = 0; i < sc.length; i++) {
        for (int j = 0; j < st.length; j++) {
            if (st[j] != '#' && st[j] == sc[i]) {
                st[j] = '#';
            }
        }
    }
    for (int j = 0; j < st.length; j++) {
        if(st[j]!='#'){
            isAnagram = false;
            break;
        }
    }
    return isAnagram;
}

思路二：当然首先判断两个字符串s和t长度是否相同，不相同直接返回false，构建一个大小为26的int 数组，遍历字符串s,统计所有字符出现的频率，遍历字符串t,操作int 数组，字符对应下标减1，直到t最后一个字符。最后如果int 数组全为0则为异位构词否则不是。

public boolean isAnagram(String s, String t) {
    boolean isAnagram = true;
    if (s.length() != t.length())
        return false;
    int[] charArr = new int[26];
    for (int i = 0; i < s.length(); i++) {
        charArr[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < t.length(); i++) {
        charArr[t.charAt(i) - 'a']--;
        if (charArr[t.charAt(i) - 'a'] !=0) {
            isAnagram = false;
            break;
        }
    }
    return isAnagram;
  }

异位构词扩展，在一组字符串中查找所有异位构词归类。

Given an array of strings, group anagrams together.For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"]

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

字符串数组异位构词分类可以借助思路二的解法，如果 eat 和 tea 为异位构词则它们对应的26 位 int nums[] 相同，借助hashCode，它们有相同的hash 值，作为HahMap 的key进行分组归类。

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> res = new ArrayList<>();
    if (strs != null) {
        Map<Integer, List<String>> kvs = new HashMap<>();
        for (String s : strs) {
            int key = getKey(s);
            if (kvs.get(key) != null) {
                kvs.get(key).add(s);
            } else {
                List<String> value = new ArrayList<>();
                value.add(s);
                kvs.put(key, value);
            }
        }
        if (kvs != null) {
            for (Integer integer : kvs.keySet()) {
                res.add(kvs.get(integer));
            }
        }
    }
    return res;
}
public int  getKey(String s) {
    int[] nums = new int[26];
    for (int i = 0; i < s.length(); i++) {
        nums[s.charAt(i) - 'a']++;
    }
    return Arrays.hashCode(nums);
}
Add a custom footer
⚠️ **GitHub.com Fallback** ⚠️