自学内容网 自学内容网

有效的变位词

        如果哈希表的键的取值范围是固定的,并且范围不是很大,则可以用数组来模拟哈希表。数组的下标和哈希表的键相对应,而数组的值和哈希表的值相对应。

        英文小写字母只有26个,因此可以用一个数组来模拟哈希表。

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length() || s.equals(t))
            return false;
        int[] arr = new int[26];
        for (char ch : s.toCharArray()){
            arr[ch - 'a']++;
        } 
        for (char ch : t.toCharArray()){
            arr[ch - 'a']--;
        }
        for (int a : arr){
            if(a != 0)
                return false;
        }
        return true;
    }
}

当然也可以用排序的方法做:首先判断字符串是否相等、长度是否不一致,如果相等或者长度不一致则直接返回 false,反之则继续判断两个字符串排序后是否相等。我们可以对字符串s和t分别排序,看排序后的字符串是否相等。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length() || s.equals(t)) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
}

        一个unicode字符长度为16位,可以表示65536个字符。当然可以继续用长度为65536的数组来模拟哈希表,不过不建议,有点浪费内存。

        此时可以使用真正的哈希表Hashmap。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length() || s.equals(t)) {
            return false;
        }
        Map<Character, Integer> counts = new HashMap<>();
        for (char ch : s.toCharArray()) {
            counts.put(ch, counts.getOrDefault(ch, 0) + 1);
        }
        for (char ch : t.toCharArray()) {
            if (!counts.containsKey(ch) || counts.get(ch) == 0){
                return false;
            }
            counts.put(ch,counts.get(ch) - 1);
        }

        return true;
    }
}


原文地址:https://blog.csdn.net/w17319185551/article/details/139183429

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!