242.有效的字母异位词

题目描述

题解

哈希表

使用哈希表结构, 先将s字符串中的所有字符都添加进去, key为字符, value为相应的频数

然后遍历t字符串, 如果当前遍历到的字符在哈希表中不存在, 直接返回false

如果当前字符在哈希表中存在, 那么分为两种情况

• value>1: 将其频数减一
• value==1: 移除该键值对

public boolean isAnagram(String s, String t) {
    if (s.length()!=t.length()){
        return false;
    }
    char[] sChars = s.toCharArray();
    char[] tChars = t.toCharArray();

    HashMap<Character, Integer> map = new HashMap<>();

    for (char sChar : sChars) {
        if (!map.containsKey(sChar)){
            map.put(sChar, 1);
        }else {
            map.put(sChar, map.get(sChar)+1);
        }
    }

    for (char tChar : tChars) {
        if (!map.containsKey(tChar)){
            return false;
        }else {
            if (map.get(tChar)>1){
                map.put(tChar, map.get(tChar)-1);
            }else if (map.get(tChar)==1){
                map.remove(tChar);
            }
        }
    }

    return map.keySet().isEmpty();
}

用数组代替哈希表

因为题目已经说明只含有小写字母, 那么可以使用一个26位的数组来记录每个字母的频数, 最后遍历该数组, 只要有个数字不为0, 就返回false

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    int[] map = new int[26];
    for (int i = 0; i < s.length(); i++) {
        map[s.charAt(i)-'a']++;
        map[t.charAt(i)-'a']--;
    }

    for (int i : map) {
        if (i!=0){
            return false;
        }
    }

    return true;
}

快排

将两个字符串排序, 如果两个字符串排序后的结果是相同的, 那么返回true, 否则返回false

public boolean isAnagram2(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    char[] sChars = s.toCharArray();
    char[] tChars = t.toCharArray();

    quickSort(sChars, 0, sChars.length - 1);
    quickSort(tChars, 0, tChars.length - 1);

    for (int i = 0; i < sChars.length; i++) {
        if (sChars[i]!=tChars[i]){
            return false;
        }
    }
    return true;
}


private void quickSort(char[] charList, int left, int right) {
    if (left > right) {
        return;
    }

    int pIndex = partition(charList, left, right);
    quickSort(charList, left, pIndex - 1);
    quickSort(charList, pIndex + 1, right);
}

private int partition(char[] charList, int left, int right) {
    char pivot = charList[left];
    int lt = left;
    for (int i = left + 1; i <= right; i++) {
        if (charList[i]<pivot){
            lt++;
            swap(charList, lt, i);
        }
    }
    swap(charList, lt, left);
    return lt;
}

private void swap(char[] numsStr, int i, int j) {
    char temp = numsStr[i];
    numsStr[i] = numsStr[j];
    numsStr[j] = temp;
}