有效的字母异位词

有效的字母异位词

Hash 集合

  • 数组
  • HashSet

HashSet 是基于 HashMap 开发出来的集合，允许有 null 值，但不允许有重复元素存在。

  • HashMap

HashMap 是一个散列表，存储结构为 key--value。

Hash 表的底层原理

Hash 表存储结构，存储的是值用过 hash 算法算出来的 HashCode ，将 HashCode 值存储在Hash表中，所以hash表是无序的，查找时间消耗为O(1);

Hash 碰撞

当有两个元素要插入 hash表 同一位置时，此时称这种情况为 hash碰撞

解决方法：

  1. 拉链法：即设立 hash表 时，使表长度尽可能满足需求。
  2. 线性探测：当碰撞时，后者向下探寻到没有被使用的空间，存储在第一个寻找到的空间中。

题目解析

此题就是验证两个字符串是不是由相同的字母根据不同顺序构成。使用一个判断数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length())
            return false;

        int[] res = new int[26];

        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();

        for(char c : str1){
            res[c-'a']++;
        }
        for(char c : str2){
            res[c-'a']--;
        }

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

        return true;
    }
}